@@ -15,6 +15,7 @@
  * get the object sha1 from the main index.
  */
 
+#ifdef DUMMY
 /*
  * This is a least-significant-digit radix sort.
  *

@@ -112,6 +113,65 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)
 #undef BUCKETS
 #undef DIGIT_SIZE
 }
+#endif
+
+static inline void swap(struct revindex_entry *a, int i, int j)
+{
+	struct revindex_entry t;
+
+	t = a[i];
+	a[i] = a[j];
+	a[j] = t;
+}
+
+/*
+ * assume that elements first .. last (array index first-1 .. last-1) obey
+ * the partially ordered tree property, except possibly for the children of
+ * the first element. push down the first element until the partially
+ * ordered tree property is restored.
+ */
+static void push_down(struct revindex_entry *a, int first, int last)
+{
+	int parent = first;
+	int last_node = last / 2;
+
+	while (parent <= last_node) {
+
+		int left = 2 * parent;
+		int right = left + 1;
+		int biggest;
+
+		if (right > last) /* parent only has one child */
+			biggest = left;
+		else {
+			if (a[left-1].offset >= a[right-1].offset)
+				biggest = left;
+			else
+				biggest = right;
+
+		}
+
+		if (a[parent-1].offset >= a[biggest-1].offset)
+			break; /* partially ordered tree property, we're done */
+
+		/* push parent down */
+		swap(a, parent-1, biggest-1);
+		parent = biggest;
+	}
+}
+
+static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)
+{
+	int i;
+
+	for (i = n/2; i > 0; i--)
+		push_down(entries, i, n);
+
+	for (i = n; i > 1; i--) {
+		swap(entries, 0, i-1);
+		push_down(entries, 1, i-1);
+	}
+}
 
 /*
  * Ordered list of offsets of objects in the pack.