merge sort
// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en // @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html function merge(list, start, midpoint, end) { const left = list.slice(start, midpoint); const right = list.slice(midpoint, end); for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) { if (topLeft >= left.length) { list[i] = right[topRight++]; } else if (topRight >= right.length) { list[i] = left[topLeft++]; } else if (left[topLeft] < right[topRight]) { list[i] = left[topLeft++]; } else { list[i] = right[topRight++]; } } } function mergesort(list, start = 0, end = undefined) { if (end === undefined) { end = list.length; } if (end - start > 1) { const midpoint = ((end + start) / 2) >> 0; mergesort(list, start, midpoint); mergesort(list, midpoint, end); merge(list, start, midpoint, end); } return list; } mergesort([4, 7, 2, 6, 4, 1, 8, 3]);