Last change
on this file since ceaed42 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago |
initial commit
|
-
Property mode
set to
100644
|
File size:
1.2 KB
|
Line | |
---|
1 | // TODO: use something more complex like timsort?
|
---|
2 | var floor = Math.floor;
|
---|
3 |
|
---|
4 | var mergeSort = function (array, comparefn) {
|
---|
5 | var length = array.length;
|
---|
6 | var middle = floor(length / 2);
|
---|
7 | return length < 8 ? insertionSort(array, comparefn) : merge(
|
---|
8 | mergeSort(array.slice(0, middle), comparefn),
|
---|
9 | mergeSort(array.slice(middle), comparefn),
|
---|
10 | comparefn
|
---|
11 | );
|
---|
12 | };
|
---|
13 |
|
---|
14 | var insertionSort = function (array, comparefn) {
|
---|
15 | var length = array.length;
|
---|
16 | var i = 1;
|
---|
17 | var element, j;
|
---|
18 |
|
---|
19 | while (i < length) {
|
---|
20 | j = i;
|
---|
21 | element = array[i];
|
---|
22 | while (j && comparefn(array[j - 1], element) > 0) {
|
---|
23 | array[j] = array[--j];
|
---|
24 | }
|
---|
25 | if (j !== i++) array[j] = element;
|
---|
26 | } return array;
|
---|
27 | };
|
---|
28 |
|
---|
29 | var merge = function (left, right, comparefn) {
|
---|
30 | var llength = left.length;
|
---|
31 | var rlength = right.length;
|
---|
32 | var lindex = 0;
|
---|
33 | var rindex = 0;
|
---|
34 | var result = [];
|
---|
35 |
|
---|
36 | while (lindex < llength || rindex < rlength) {
|
---|
37 | if (lindex < llength && rindex < rlength) {
|
---|
38 | result.push(comparefn(left[lindex], right[rindex]) <= 0 ? left[lindex++] : right[rindex++]);
|
---|
39 | } else {
|
---|
40 | result.push(lindex < llength ? left[lindex++] : right[rindex++]);
|
---|
41 | }
|
---|
42 | } return result;
|
---|
43 | };
|
---|
44 |
|
---|
45 | module.exports = mergeSort;
|
---|
Note:
See
TracBrowser
for help on using the repository browser.