-
-
-#define partition(ref, field, key, ascending) \
- while (i <= j) { \
- if (ascending) { \
- while (ref[i].field < key) \
- i++; \
- while (ref[j].field > key) \
- j--; \
- } else { \
- while (ref[i].field > key) \
- i++; \
- while (ref[j].field < key) \
- j--; \
- } \
- if (i <= j) { \
- tmp = ref[i]; \
- ref[i] = ref[j]; \
- ref[j] = tmp; \
- i++; \
- j--; \
- } \
- } \
-
-static void sort_one(VAPictureH264 ref[], int left, int right,
- int ascending, int frame_idx)
-{
- int i = left, j = right;
- unsigned int key;
- VAPictureH264 tmp;
-
- if (frame_idx) {
- key = ref[(left + right) / 2].frame_idx;
- partition(ref, frame_idx, key, ascending);
- } else {
- key = ref[(left + right) / 2].TopFieldOrderCnt;
- partition(ref, TopFieldOrderCnt, (signed int)key, ascending);
- }
-
- /* recursion */
- if (left < j)
- sort_one(ref, left, j, ascending, frame_idx);
-
- if (i < right)
- sort_one(ref, i, right, ascending, frame_idx);
-}
-
-static void sort_two(VAPictureH264 ref[], int left, int right, unsigned int key, unsigned int frame_idx,
- int partition_ascending, int list0_ascending, int list1_ascending)
+// Given a list like 1 9 3 0 2 8 4 and a pivot element 3, will produce
+//
+// 2 1 0 [3] 4 8 9
+template<class T, class C>
+static void sort_two(T *begin, T *end, const T &pivot, const C &less_than)