// bottomUpMergeSort.mjs // Stable bottom-up merge sort (ES module) /** * Bottom-up stable merge sort (iterative) with an optional comparator. * - Default comparator follows Array.prototype.sort style: return <0, 0, >0 * - Stable: preserves relative order of equal elements * - Reuses a single temporary buffer for all merges * * @param {Array} arr - Array to sort in place * @param {Function} comparator - Optional comparator (a, b) => number * @returns {Array} The sorted array (same reference as input) */ export function bottomUpMergeSort(arr, comparator = defaultComparator) { const n = arr.length; if (n <= 1) return arr; const cmp = normalizeComparator(comparator); const temp = new Array(n); for (let width = 1; width < n; width *= 2) { for (let left = 0; left < n; left += 2 * width) { const mid = Math.min(left + width, n); const right = Math.min(left + 2 * width, n); if (mid < right) { mergeIntoTemp(arr, temp, left, mid, right, cmp); } } } return arr; } /** * Non-mutating convenience wrapper * @param {Array} arr * @param {Function} comparator * @returns {Array} */ export function bottomUpMergeSortCopy(arr, comparator) { return bottomUpMergeSort([...arr], comparator); } /** * Merge two adjacent sorted ranges [left, mid) and [mid, right) * Uses temp buffer and writes merged result back into arr[left..right-1]. * Stability: when comparator returns 0, element from left is taken first. */ function mergeIntoTemp(arr, temp, left, mid, right, cmp) { let i = left; let j = mid; let k = left; while (i < mid && j < right) { const comparison = cmp(arr[i], arr[j]); if (comparison <= 0) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i < mid) temp[k++] = arr[i++]; while (j < right) temp[k++] = arr[j++]; for (let idx = left; idx < right; idx++) { arr[idx] = temp[idx]; } } /** * Normalize comparator to a function that returns negative/zero/positive. * Accepts: * - comparator(a, b) => number (standard) * - comparator(a, b) => boolean (true if a < b) for backward compatibility */ function normalizeComparator(comparator) { if (typeof comparator !== 'function') return defaultComparator; try { const test = comparator(0, 1); if (typeof test === 'boolean') { return (a, b) => (comparator(a, b) ? -1 : comparator(b, a) ? 1 : 0); } } catch { // Fall back to default if comparator throws on sample inputs } return comparator; } /** * Default comparator that mirrors Array.prototype.sort for common types. */ function defaultComparator(a, b) { if (a === b) return 0; return a < b ? -1 : 1; } // Optional: small test harness when run in Node directly if (typeof process !== 'undefined' && process && process.argv && require.main === module) { runTests(); } function runTests() { const perf = getPerformance(); console.log('Empty array:', bottomUpMergeSortCopy([])); console.log('Single element:', bottomUpMergeSortCopy([5])); console.log('Already sorted:', bottomUpMergeSortCopy([1, 2, 3, 4, 5])); console.log('Reverse sorted:', bottomUpMergeSortCopy([5, 4, 3, 2, 1])); console.log('Random order:', bottomUpMergeSortCopy([3, 7, 1, 9, 2, 8, 4, 6, 5])); console.log('Duplicates:', bottomUpMergeSortCopy([3, 1, 4, 1, 5, 9, 2, 6, 5])); const objects = [ { value: 3, id: 'a' }, { value: 1, id: 'b' }, { value: 3, id: 'c' }, { value: 1, id: 'd' }, { value: 2, id: 'e' } ]; console.log('Objects sorted by value (stability):', bottomUpMergeSortCopy(objects, (x, y) => x.value - y.value)); const large = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 10000)); const t0 = perf.now(); const sortedLarge = bottomUpMergeSortCopy(large); const t1 = perf.now(); console.log(`Sorted ${large.length} elements in ${(t1 - t0).toFixed(2)}ms`); console.log('First 10:', sortedLarge.slice(0, 10)); console.log('Last 10:', sortedLarge.slice(-10)); } function getPerformance() { if (typeof performance !== 'undefined' && performance && typeof performance.now === 'function') { return performance; } try { const { performance: perf } = require('perf_hooks'); return perf; } catch { return { now: () => Date.now() }; } } 

<script type="module"> import { bottomUpMergeSortCopy } from './bottomUpMergeSort.mjs'; const data = [9, 4, 6, 1]; console.log(bottomUpMergeSortCopy(data)); </script>