Sort It Out A song about sorting algorithms

Subject
Computer science
Genre
Hip-hop
Level
College
Length
1:52
Tempo
90 BPM

More on this topic

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

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.

  1. 1What is the worst-case time complexity of bubble, insertion and selection sort?

    O(n²).

  2. 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.

  3. 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.

  4. 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.

Welcome to BrainBeats

Sign in or create your free account

No password needed. Pick Google, or we’ll email you a sign-in link.

Continue with Google

or

Part of BrainBeats Plus

Unlock this song

Start your free week

7 days free, then $5.99/month billed yearly. Cancel anytime.

or

Play a free song