[FFmpeg-cvslog] libavutil: add a merge sort.

[Michael Niedermayer]

ffmpeg | branch: master | Michael Niedermayer <michaelni at gmx.at> | Mon Jun 18 18:40:02 2012 +0200| [f87dacb27de93f995cb18f9dcc73581ef8fc157b] | committer: Michael Niedermayer

libavutil: add a merge sort.

compared to qsort this is slower but its stable and doesnt have a O(n^2) worst
case

Signed-off-by: Michael Niedermayer <michaelni at gmx.at>

> http://git.videolan.org/gitweb.cgi/ffmpeg.git/?a=commit;h=f87dacb27de93f995cb18f9dcc73581ef8fc157b
---

 libavutil/qsort.h |   25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/libavutil/qsort.h b/libavutil/qsort.h
index a9ab1f3..089eb74 100644
--- a/libavutil/qsort.h
+++ b/libavutil/qsort.h
@@ -90,3 +90,28 @@
         }\
     }\
 }
+
+/**
+ * Merge sort, this sort requires a temporary buffer and is stable, its worst
+ * case time is O(n log n)
+ * @param p     must be a lvalue pointer, this function may exchange it with tmp
+ * @param tmp   must be a lvalue pointer, this function may exchange it with p
+ */
+#define AV_MSORT(p, tmp, num, type, cmp) {\
+    unsigned i, j, step;\
+    for(step=1; step<(num); step+=step){\
+        for(i=0; i<(num); i+=2*step){\
+            unsigned a[2] = {i, i+step};\
+            unsigned end = FFMIN(i+2*step, (num));\
+            for(j=i; a[0]<i+step && a[1]<end; j++){\
+                int idx= cmp(p+a[0], p+a[1]) < 0;\
+                tmp[j] = p[ a[idx]++ ];\
+            }\
+            if(a[0]>=i+step) a[0] = a[1];\
+            for(; j<end; j++){\
+                tmp[j] = p[ a[0]++ ];\
+            }\
+        }\
+        FFSWAP(type*, p, tmp);\
+    }\
+}