| | |
| | | // TODO: use something more complex like timsort? |
| | | var arraySlice = require('../internals/array-slice-simple'); |
| | | |
| | | var floor = Math.floor; |
| | | |
| | | var mergeSort = function (array, comparefn) { |
| | | var length = array.length; |
| | | var middle = floor(length / 2); |
| | | return length < 8 ? insertionSort(array, comparefn) : merge( |
| | | mergeSort(array.slice(0, middle), comparefn), |
| | | mergeSort(array.slice(middle), comparefn), |
| | | array, |
| | | mergeSort(arraySlice(array, 0, middle), comparefn), |
| | | mergeSort(arraySlice(array, middle), comparefn), |
| | | comparefn |
| | | ); |
| | | }; |
| | |
| | | } return array; |
| | | }; |
| | | |
| | | var merge = function (left, right, comparefn) { |
| | | var merge = function (array, left, right, comparefn) { |
| | | var llength = left.length; |
| | | var rlength = right.length; |
| | | var lindex = 0; |
| | | var rindex = 0; |
| | | var result = []; |
| | | |
| | | while (lindex < llength || rindex < rlength) { |
| | | if (lindex < llength && rindex < rlength) { |
| | | result.push(comparefn(left[lindex], right[rindex]) <= 0 ? left[lindex++] : right[rindex++]); |
| | | } else { |
| | | result.push(lindex < llength ? left[lindex++] : right[rindex++]); |
| | | } |
| | | } return result; |
| | | array[lindex + rindex] = (lindex < llength && rindex < rlength) |
| | | ? comparefn(left[lindex], right[rindex]) <= 0 ? left[lindex++] : right[rindex++] |
| | | : lindex < llength ? left[lindex++] : right[rindex++]; |
| | | } return array; |
| | | }; |
| | | |
| | | module.exports = mergeSort; |