1 |
|
2 |
|
3 | |
4 |
|
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 |
|
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 | module.exports = mergeSort;
|
54 |
|
55 |
|