Sorting Algorithms
Comparison sorts put data in order by repeatedly comparing and rearranging elements, trading O(n squared) simplicity against O(n log n) efficiency.
Loading visual…
Definition
A sorting algorithm rearranges the elements of a collection into an order defined by a comparison rule, usually smallest to largest. Simple sorts such as bubble sort and insertion sort repeatedly compare neighboring elements and swap the ones that are out of order; each full pass moves at least one element into its final position, so sorting n elements takes roughly n times n comparisons in the worst case, an O(n squared) algorithm. These sorts are easy to reason about and work well on small or nearly sorted inputs, but the cost grows quickly as the input grows. Divide and conquer sorts such as merge sort instead split the input in half, sort each half recursively, and then merge the two sorted halves back together in a single linear pass. Because the input is halved at every level and each level only does O(n) work to merge, the total cost is O(n log n), which is the best any comparison based sort can do: no algorithm that only compares pairs of elements can sort in fewer than roughly n log n comparisons in the worst case. Quicksort follows a similar divide and conquer shape but partitions around a pivot instead of merging, averaging O(n log n) time with no extra memory, at the cost of an O(n squared) worst case on unlucky pivots. JavaScript's built in Array.prototype.sort mutates the array in place and, without a comparator function, converts every element to a string and sorts lexicographically, so [10, 2, 1].sort() produces [1, 10, 2] instead of numeric order. Passing a comparator such as (a, b) => a - b restores numeric ordering, and modern engines guarantee the sort is stable, meaning elements that compare equal keep their original relative order.
Examples
function bubbleSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
bubbleSort([5, 2, 4, 1]); // [1, 2, 4, 5]Each inner pass compares neighbors and swaps the larger one rightward, so after i passes the i largest values have bubbled to the end; the nested loops make this O(n squared).
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
const merged = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
merged.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return [...merged, ...left.slice(i), ...right.slice(j)];
}
mergeSort([5, 2, 4, 1]); // [1, 2, 4, 5]The array splits in half recursively until each piece has one element, then merge combines pairs of already sorted pieces by comparing their fronts, giving O(n log n) time overall.
[10, 2, 1].sort(); // ['1', '10', '2'], lexicographic
[10, 2, 1].sort((a, b) => a - b); // [1, 2, 10], numericWithout a comparator, sort converts values to strings and compares them character by character; supplying (a, b) => a - b tells it to compare numerically instead.
Common mistakes
- Assuming Array.prototype.sort() sorts numbers correctly without a comparator; by default it sorts lexicographically as strings.
- Reaching for a nested loop sort on large inputs when an O(n log n) sort would finish far sooner.
- Forgetting that Array.prototype.sort() mutates the original array in place, which can surprise code that expected a new array.
Key takeaways
- Comparison sorts cannot beat O(n log n) in the worst case; O(n squared) sorts trade speed for simplicity.
- Divide and conquer sorts like merge sort split the problem in half and combine sorted pieces in linear time.
- JavaScript's sort needs an explicit comparator for numeric or custom ordering.
- A stable sort preserves the relative order of elements that compare equal.
Why can no comparison based sorting algorithm do better than O(n log n) in the worst case?
Where you see this
- Ordering search results or leaderboard entries by score before displaying them.
- Preparing a dataset for binary search, which only works correctly on sorted input.
- Grouping or deduplicating records by sorting on a key first so equal keys sit next to each other.
- Sorting log entries by timestamp to reconstruct the order events occurred.