1 files changed, 24 insertions, 0 deletions
diff --git a/lib/utils.js b/lib/utils.js
index 6a73c714..e9a2f80a 100644
--- a/lib/utils.js
+++ b/lib/utils.js
@@ -151,3 +151,27 @@ function string_template(text, props) {
         return props[p];
     });
 };
+
+function mergeSort(array, cmp) {
+    if (array.length < 2) return array.slice();
+    function merge(a, b) {
+        var r = [], ai = 0, bi = 0, i = 0;
+        while (ai < a.length && bi < b.length) {
+            cmp(a[ai], b[bi]) <= 0
+                ? r[i++] = a[ai++]
+                : r[i++] = b[bi++];
+        }
+        if (ai < a.length) r.push.apply(r, a.slice(ai));
+        if (bi < b.length) r.push.apply(r, b.slice(bi));
+        return r;
+    };
+    function _ms(a) {
+        if (a.length <= 1)
+            return a;
+        var m = Math.floor(a.length / 2), left = a.slice(0, m), right = a.slice(m);
+        left = _ms(left);
+        right = _ms(right);
+        return merge(left, right);
+    };
+    return _ms(array);
+};