review.tizen.org Git - platform/framework/web/crosswalk-tizen.git/blob

   1 define(function () {
   2
   3     /**
   4      * Merge sort (http://en.wikipedia.org/wiki/Merge_sort)
   5      */
   6     function mergeSort(arr, compareFn) {
   7         if (arr == null) {
   8             return [];
   9         } else if (arr.length < 2) {
  10             return arr;
  11         }
  12
  13         if (compareFn == null) {
  14             compareFn = defaultCompare;
  15         }
  16
  17         var mid, left, right;
  18
  19         mid   = ~~(arr.length / 2);
  20         left  = mergeSort( arr.slice(0, mid), compareFn );
  21         right = mergeSort( arr.slice(mid, arr.length), compareFn );
  22
  23         return merge(left, right, compareFn);
  24     }
  25
  26     function defaultCompare(a, b) {
  27         return a < b ? -1 : (a > b? 1 : 0);
  28     }
  29
  30     function merge(left, right, compareFn) {
  31         var result = [];
  32
  33         while (left.length && right.length) {
  34             if (compareFn(left[0], right[0]) <= 0) {
  35                 // if 0 it should preserve same order (stable)
  36                 result.push(left.shift());
  37             } else {
  38                 result.push(right.shift());
  39             }
  40         }
  41
  42         if (left.length) {
  43             result.push.apply(result, left);
  44         }
  45
  46         if (right.length) {
  47             result.push.apply(result, right);
  48         }
  49
  50         return result;
  51     }
  52
  53     return mergeSort;
  54
  55 });