| //! stable.js 0.1.8, https://github.com/Two-Screen/stable |
| //! © 2018 Angry Bytes and contributors. MIT licensed. |
| |
| (function (global, factory) { |
| typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() : |
| typeof define === 'function' && define.amd ? define(factory) : |
| (global.stable = factory()); |
| }(this, (function () { 'use strict'; |
| |
| // A stable array sort, because `Array#sort()` is not guaranteed stable. |
| // This is an implementation of merge sort, without recursion. |
| |
| var stable = function (arr, comp) { |
| return exec(arr.slice(), comp) |
| }; |
| |
| stable.inplace = function (arr, comp) { |
| var result = exec(arr, comp); |
| |
| // This simply copies back if the result isn't in the original array, |
| // which happens on an odd number of passes. |
| if (result !== arr) { |
| pass(result, null, arr.length, arr); |
| } |
| |
| return arr |
| }; |
| |
| // Execute the sort using the input array and a second buffer as work space. |
| // Returns one of those two, containing the final result. |
| function exec(arr, comp) { |
| if (typeof(comp) !== 'function') { |
| comp = function (a, b) { |
| return String(a).localeCompare(b) |
| }; |
| } |
| |
| // Short-circuit when there's nothing to sort. |
| var len = arr.length; |
| if (len <= 1) { |
| return arr |
| } |
| |
| // Rather than dividing input, simply iterate chunks of 1, 2, 4, 8, etc. |
| // Chunks are the size of the left or right hand in merge sort. |
| // Stop when the left-hand covers all of the array. |
| var buffer = new Array(len); |
| for (var chk = 1; chk < len; chk *= 2) { |
| pass(arr, comp, chk, buffer); |
| |
| var tmp = arr; |
| arr = buffer; |
| buffer = tmp; |
| } |
| |
| return arr |
| } |
| |
| // Run a single pass with the given chunk size. |
| var pass = function (arr, comp, chk, result) { |
| var len = arr.length; |
| var i = 0; |
| // Step size / double chunk size. |
| var dbl = chk * 2; |
| // Bounds of the left and right chunks. |
| var l, r, e; |
| // Iterators over the left and right chunk. |
| var li, ri; |
| |
| // Iterate over pairs of chunks. |
| for (l = 0; l < len; l += dbl) { |
| r = l + chk; |
| e = r + chk; |
| if (r > len) r = len; |
| if (e > len) e = len; |
| |
| // Iterate both chunks in parallel. |
| li = l; |
| ri = r; |
| while (true) { |
| // Compare the chunks. |
| if (li < r && ri < e) { |
| // This works for a regular `sort()` compatible comparator, |
| // but also for a simple comparator like: `a > b` |
| if (comp(arr[li], arr[ri]) <= 0) { |
| result[i++] = arr[li++]; |
| } |
| else { |
| result[i++] = arr[ri++]; |
| } |
| } |
| // Nothing to compare, just flush what's left. |
| else if (li < r) { |
| result[i++] = arr[li++]; |
| } |
| else if (ri < e) { |
| result[i++] = arr[ri++]; |
| } |
| // Both iterators are at the chunk ends. |
| else { |
| break |
| } |
| } |
| } |
| }; |
| |
| return stable; |
| |
| }))); |