diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 2d2aabc..3355c41 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -46,6 +46,7 @@
 using std::max;
 using std::min;
 using std::set;
+using std::sort;
 using std::string;
 using std::unique_ptr;
 using std::vector;
@@ -298,6 +299,19 @@
   return removed_bytes;
 }
 
+// Compare two AnnotatedOperations by the start block of the first Extent in
+// their destination extents.
+bool CompareAopsByDestination(AnnotatedOperation first_aop,
+                              AnnotatedOperation second_aop) {
+  // We want empty operations to be at the end of the payload.
+  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
+    return ((!first_aop.op.dst_extents().size()) <
+            (!second_aop.op.dst_extents().size()));
+  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
+  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
+  return first_dst_start < second_dst_start;
+}
+
 }  // namespace
 
 bool DeltaDiffGenerator::DeltaReadFiles(Graph* graph,
@@ -1043,7 +1057,6 @@
     rootfs_ops->back().name = unwritten_vertex.file_name;
   }
 
-  // Fragment operations so we can sort them later.
   TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
                                            config.target.rootfs_part,
                                            data_file_fd,
@@ -1052,6 +1065,8 @@
                                            config.target.rootfs_part,
                                            data_file_fd,
                                            data_file_size));
+  SortOperationsByDestination(rootfs_ops);
+  SortOperationsByDestination(kernel_ops);
 
   return true;
 }
@@ -1340,10 +1355,11 @@
   *extents = new_extents;
 }
 
-bool DeltaDiffGenerator::FragmentOperations(vector<AnnotatedOperation>* aops,
-                                            const string& target_rootfs_part,
-                                            int data_fd,
-                                            off_t* data_file_size) {
+bool DeltaDiffGenerator::FragmentOperations(
+    vector<AnnotatedOperation>* aops,
+    const string& target_rootfs_part,
+    int data_fd,
+    off_t* data_file_size) {
   vector<AnnotatedOperation> fragmented_aops;
   for (const AnnotatedOperation& aop : *aops) {
     if (aop.op.type() ==
@@ -1367,6 +1383,11 @@
   return true;
 }
 
+void DeltaDiffGenerator::SortOperationsByDestination(
+    vector<AnnotatedOperation>* aops) {
+  sort(aops->begin(), aops->end(), CompareAopsByDestination);
+}
+
 bool DeltaDiffGenerator::SplitSourceCopy(
     const AnnotatedOperation& original_aop,
     vector<AnnotatedOperation>* result_aops) {
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 6b4dc63..d34b9da 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -234,13 +234,18 @@
 
   // Takes a vector of AnnotatedOperations |aops| and fragments those operations
   // such that there is only one dst extent per operation. Sets |aops| to a
-  // vector of the new fragmented operations. This is only called when delta
-  // minor version is 2.
+  // vector of the new fragmented operations.
   static bool FragmentOperations(std::vector<AnnotatedOperation>* aops,
                                  const std::string& target_rootfs_part,
                                  int data_fd,
                                  off_t* data_file_size);
 
+  // Takes a vector of AnnotatedOperations |aops| and sorts them by the first
+  // start block in their destination extents. Sets |aops| to a vector of the
+  // sorted operations.
+  static void SortOperationsByDestination(
+      std::vector<AnnotatedOperation>* aops);
+
   // Takes an SOURCE_COPY install operation, |aop|, and adds one operation for
   // each dst extent in |aop| to |ops|. The new operations added to |ops| will
   // have only one dst extent. The src extents are split so the number of blocks
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index fe15516..d62a4de 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -1001,5 +1001,38 @@
   EXPECT_EQ(data_file_size, second_op.data_offset() + second_op.data_length());
 }
 
+TEST_F(DeltaDiffGeneratorTest, SortOperationsByDestinationTest) {
+  vector<AnnotatedOperation> aops;
+  // One operation with multiple destination extents.
+  DeltaArchiveManifest_InstallOperation first_op;
+  *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
+  *(first_op.add_dst_extents()) = ExtentForRange(10, 2);
+  AnnotatedOperation first_aop;
+  first_aop.op = first_op;
+  first_aop.name = "first";
+  aops.push_back(first_aop);
+
+  // One with no destination extent. Should end up at the end of the vector.
+  DeltaArchiveManifest_InstallOperation second_op;
+  AnnotatedOperation second_aop;
+  second_aop.op = second_op;
+  second_aop.name = "second";
+  aops.push_back(second_aop);
+
+  // One with one destination extent.
+  DeltaArchiveManifest_InstallOperation third_op;
+  *(third_op.add_dst_extents()) = ExtentForRange(3, 2);
+  AnnotatedOperation third_aop;
+  third_aop.op = third_op;
+  third_aop.name = "third";
+  aops.push_back(third_aop);
+
+  DeltaDiffGenerator::SortOperationsByDestination(&aops);
+  EXPECT_EQ(aops.size(), 3);
+  EXPECT_EQ(third_aop.name, aops[0].name);
+  EXPECT_EQ(first_aop.name, aops[1].name);
+  EXPECT_EQ(second_aop.name, aops[2].name);
+}
+
 
 }  // namespace chromeos_update_engine