Two sorted piles
Merging two already-sorted piles is easy: keep taking the smaller top card. Divide and conquer turns that into a full sort: split the list in half, sort each half the same way, merge. There are log n levels of halving and each level does O(n) merging: O(n log n).
Merge sort
function merge(left, right) {
const out = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) out.push(left[i++]);
else out.push(right[j++]);
}
while (i < left.length) out.push(left[i++]);
while (j < right.length) out.push(right[j++]);
return out;
}
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
const big = Array.from({ length: 200000 }, () => Math.floor(Math.random() * 1e6));
const t = performance.now();
mergeSort(big);
console.log("200,000 numbers sorted in", Math.round(performance.now() - t), "ms");