Insertion sort in JavaScript
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
insertionSort.js, 21 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/insertion-sort/. The authors are listed in prov/3NS7RT.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 insertionSort(a) {
for (let i = 1; i < a.length; i++) { // @line L1
const key = a[i]; // @line L2
let j = i - 1; // @line L3
while (j >= 0 && a[j] > key) { // @line L4
a[j + 1] = a[j]; // @line L5
j--; // @line L6
}
a[j + 1] = key; // @line L7
}
return a;
}
insertionSort.test.js 30 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
import { test } from "node:test";
import assert from "node:assert/strict";
import { insertionSort } from "./insertionSort.js";
test("example", () => {
assert.deepEqual(insertionSort([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]);
});
test("edges", () => {
assert.deepEqual(insertionSort([]), []);
assert.deepEqual(insertionSort([1]), [1]);
assert.deepEqual(insertionSort([3, 2, 1, 1]), [1, 1, 2, 3]);
assert.deepEqual(insertionSort(["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(41) }, () => next(101) - 50);
const want = [...a].sort((p, q) => p - q);
assert.deepEqual(insertionSort([...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