diff --git a/tools/releasetools/blockimgdiff.py b/tools/releasetools/blockimgdiff.py
index 70bb4eb..662b4ec 100644
--- a/tools/releasetools/blockimgdiff.py
+++ b/tools/releasetools/blockimgdiff.py
@@ -999,8 +999,11 @@
       heap.append(xf.heap_item)
     heapq.heapify(heap)
 
-    sinks = set(u for u in G if not u.outgoing)
-    sources = set(u for u in G if not u.incoming)
+    # Use OrderedDict() instead of set() to preserve the insertion order. Need
+    # to use 'sinks[key] = None' to add key into the set. sinks will look like
+    # { key1: None, key2: None, ... }.
+    sinks = OrderedDict.fromkeys(u for u in G if not u.outgoing)
+    sources = OrderedDict.fromkeys(u for u in G if not u.incoming)
 
     def adjust_score(iu, delta):
       iu.score += delta
@@ -1011,26 +1014,28 @@
     while G:
       # Put all sinks at the end of the sequence.
       while sinks:
-        new_sinks = set()
+        new_sinks = OrderedDict()
         for u in sinks:
           if u not in G: continue
           s2.appendleft(u)
           del G[u]
           for iu in u.incoming:
             adjust_score(iu, -iu.outgoing.pop(u))
-            if not iu.outgoing: new_sinks.add(iu)
+            if not iu.outgoing:
+              new_sinks[iu] = None
         sinks = new_sinks
 
       # Put all the sources at the beginning of the sequence.
       while sources:
-        new_sources = set()
+        new_sources = OrderedDict()
         for u in sources:
           if u not in G: continue
           s1.append(u)
           del G[u]
           for iu in u.outgoing:
             adjust_score(iu, +iu.incoming.pop(u))
-            if not iu.incoming: new_sources.add(iu)
+            if not iu.incoming:
+              new_sources[iu] = None
         sources = new_sources
 
       if not G: break
@@ -1049,11 +1054,13 @@
       del G[u]
       for iu in u.outgoing:
         adjust_score(iu, +iu.incoming.pop(u))
-        if not iu.incoming: sources.add(iu)
+        if not iu.incoming:
+          sources[iu] = None
 
       for iu in u.incoming:
         adjust_score(iu, -iu.outgoing.pop(u))
-        if not iu.outgoing: sinks.add(iu)
+        if not iu.outgoing:
+          sinks[iu] = None
 
     # Now record the sequence in the 'order' field of each transfer,
     # and by rearranging self.transfers to be in the chosen sequence.
@@ -1072,8 +1079,7 @@
 
     # Each item of source_ranges will be:
     #   - None, if that block is not used as a source,
-    #   - a transfer, if one transfer uses it as a source, or
-    #   - a set of transfers.
+    #   - an ordered set of transfers.
     source_ranges = []
     for b in self.transfers:
       for s, e in b.src_ranges:
@@ -1081,23 +1087,19 @@
           source_ranges.extend([None] * (e-len(source_ranges)))
         for i in range(s, e):
           if source_ranges[i] is None:
-            source_ranges[i] = b
+            source_ranges[i] = OrderedDict.fromkeys([b])
           else:
-            if not isinstance(source_ranges[i], set):
-              source_ranges[i] = set([source_ranges[i]])
-            source_ranges[i].add(b)
+            source_ranges[i][b] = None
 
     for a in self.transfers:
-      intersections = set()
+      intersections = OrderedDict()
       for s, e in a.tgt_ranges:
         for i in range(s, e):
           if i >= len(source_ranges): break
-          b = source_ranges[i]
-          if b is not None:
-            if isinstance(b, set):
-              intersections.update(b)
-            else:
-              intersections.add(b)
+          # Add all the Transfers in source_ranges[i] to the (ordered) set.
+          if source_ranges[i] is not None:
+            for j in source_ranges[i]:
+              intersections[j] = None
 
       for b in intersections:
         if a is b: continue