Sort It Out A song about sorting algorithms
Sing it back
Can you finish the lyrics?
Eight quick questions on “Sort It Out”. No music, just your memory. Then share your score and challenge a friend.
Sorting algorithms in one paragraph
A sorting algorithm puts a list of items in order, and the classic ones differ in how their running time grows with the number of items n, how much extra memory they need and whether they are stable. Bubble sort, insertion sort and selection sort are simple but take O(n²) time in the worst case, because they compare items pair by pair over many passes. Merge sort uses divide and conquer: it splits the list in half repeatedly, sorts the halves and merges them back, taking O(n log n) time in every case; it is stable but needs O(n) extra memory. Quicksort picks a pivot and partitions the list into smaller and larger items, averaging O(n log n) and sorting in place, but it degrades to O(n²) when the pivots are consistently bad. No comparison-based sort can beat O(n log n) comparisons in the worst case.
Key facts from the song
- Bubble sort swaps out-of-order neighbors, insertion sort inserts each item into a growing sorted section, and selection sort repeatedly moves the smallest remaining item to the front; all are O(n²) in the worst case.
- Merge sort divides the list into halves, sorts them and merges them, running in O(n log n) time in every case; it is stable but uses O(n) extra memory.
- Quicksort partitions around a pivot: O(n log n) on average and in place, but O(n²) in the worst case when pivots split the list badly.
- A stable sort keeps items with equal keys in their original relative order.
- Any comparison sort needs on the order of n log n comparisons in the worst case, so none can do better than O(n log n).
Where it fits in your course
- US level
- College (undergraduate)
Lyrics
Verse 1
Bubble sort walks the list and swaps each neighbor pair that’s out of place
Insertion sort slides each new item back into the sorted space
Selection sort finds the smallest left and swaps it to the front each round
All three are big O of n squared in the worst case, slowing down
Chorus
Merge sort: divide and conquer, split the list in half, then half again
Merge them back, big O of n log n in every case, my friend
Quicksort picks a pivot, partitions smaller left and bigger right
On average n log n, but n squared when the pivots aren’t right
Verse 2
A stable sort keeps equal items in the order that they came
Merge sort is stable, but quicksort usually won’t do the same
Quicksort works in place, while merge sort needs extra memory to spare
No comparison sort beats n log n in the worst case, anywhere
Chorus
Merge sort: divide and conquer, split the list in half, then half again
Merge them back, big O of n log n in every case, my friend
Quicksort picks a pivot, partitions smaller left and bigger right
On average n log n, but n squared when the pivots aren’t right
Outro
Bubble, insertion, selection, n squared; merge and quick, n log n
Pick the right sort for the job, and your data falls in line again
Sorting algorithms flashcards
Say the answer out loud, then tap the card to check it. Or test yourself quick-fire.
1What is the worst-case time complexity of bubble, insertion and selection sort?
O(n²).
2How does merge sort work, and what is its time complexity?
It splits the list into halves, sorts them and merges them back (divide and conquer), in O(n log n) time in every case.
3What is quicksort’s average and worst-case time complexity?
O(n log n) on average, O(n²) in the worst case when pivots split the list badly.
4What is a stable sort?
One that keeps items with equal keys in their original relative order.
Questions about sorting algorithms
Still wondering about something? Ask us and we’ll reply within two working days.
What is the fastest sorting algorithm?
No single algorithm is fastest for every input. For general-purpose comparison sorting, O(n log n) algorithms such as merge sort, quicksort and heapsort are the standard choice, and real libraries often use hybrids such as Timsort or introsort.
What does it mean for a sorting algorithm to be stable?
A stable sort keeps items with equal keys in the same relative order they started in. Merge sort, insertion sort and bubble sort are stable; typical quicksort and selection sort implementations are not.
Why is quicksort O(n²) in the worst case?
If the pivot is always the smallest or largest item, each partition removes only one item, so the algorithm makes about n levels of passes over the list. Choosing pivots randomly or with median-of-three makes this very unlikely in practice.
Why can’t comparison sorts beat O(n log n)?
A list of n items can be arranged in n! orders, and each comparison has only two outcomes, so at least log₂(n!) comparisons are needed in the worst case to tell them apart. log₂(n!) grows like n log n.