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
|
Rev | Line | |
---|
[6a3a178] | 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.