merge sort: O(n log n) always

Ever wondered why sorting your music library takes ages?

Imagine you're organizing your favorite songs by genre and then by artist name, but the list keeps growing.

As you add more songs, the time to sort them increases. Merge sort divides the list and sorts each part before combining them, making it faster than just comparing every song.

Example

Sorting 1,000 songs takes longer than sorting 100 songs, but merge sort handles both efficiently.

Remember this

Merge sort's time complexity is O(n log n), meaning it consistently sorts lists faster as they grow.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

O(n log n) is the lower bound for comparison-based sorting

Ever wonder why sorting can't be faster than a certain point?

Binary search

How fast can you find a word in a dictionary?

Best, worst and average case

Quicksort's average time complexity is O(n log n)

Hash table

Hash table lookup: O(1) average time complexity

Dijkstra's algorithm

Dijkstra's algorithm time complexity: O((V+E) log V)

B-trees optimize: disk-based sorted data with O(log n) reads per query

B-trees optimize disk-based sorted data with O(log n) reads per query

Swipe through 100 ML concepts daily

Open Pocket Polymath