Merge sort in JavaScript
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
mergeSort.js, 37 lines- Level
- Native tests
- pass in this build
- Toolchain
- Node.js 24, ES modules
- Test framework
- node:test
- Run the tests
node --test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
/**
* Sorts a in place, in non-decreasing order, and returns it. The sort is stable.
* @template T
* @param {T[]} a
* @returns {T[]}
*/
export function mergeSort(a) {
sort(a, 0, a.length);
return a;
}
function sort(a, lo, hi) {
if (hi - lo <= 1) return; // @line L1
const mid = lo + ((hi - lo) >> 1); // @line L2
sort(a, lo, mid); // @line L3
sort(a, mid, hi); // @line L4
merge(a, lo, mid, hi); // @line L5
}
function merge(a, lo, mid, hi) {
const b = a.slice(lo, mid); // @line L6
let i = 0, j = mid, k = lo; // @line L7
while (i < b.length && j < hi) { // @line L8
if (b[i] <= a[j]) { // @line L9
a[k] = b[i++];
} else {
a[k] = a[j++]; // @line L10
}
k++; // @line L11
}
while (i < b.length) { // @line L12
a[k++] = b[i++]; // @line L13
}
}
mergeSort.test.js 30 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
import { test } from "node:test";
import assert from "node:assert/strict";
import { mergeSort } from "./mergeSort.js";
test("example", () => {
assert.deepEqual(mergeSort([38, 27, 43, 3, 9, 82, 10]), [3, 9, 10, 27, 38, 43, 82]);
});
test("edges", () => {
assert.deepEqual(mergeSort([]), []);
assert.deepEqual(mergeSort([1]), [1]);
assert.deepEqual(mergeSort([3, 2, 1, 1]), [1, 1, 2, 3]);
assert.deepEqual(mergeSort(["pear", "fig", "apple"]), ["apple", "fig", "pear"]);
});
test("random against Array.prototype.sort", () => {
let s = 2150;
const next = (m) => {
s = (Math.imul(s, 1103515245) + 12345) >>> 0;
return (s >>> 8) % m;
};
for (let t = 0; t < 500; t++) {
const a = Array.from({ length: next(61) }, () => next(101) - 50);
const want = [...a].sort((p, q) => p - q);
assert.deepEqual(mergeSort([...a]), want);
}
});
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work