Merge Sort

noun

say it: “MURJ sort” /mɝːdʒ sɔːrt/

A sort that splits a list in half, sorts each half the same way, then merges the two sorted halves into one.

What is merge sort?

Merge sort splits a list in half, sorts each half with merge sort, then merges the two sorted halves by always taking the smaller front item, like friends splitting a deck of cards and merging their sorted piles. There are about log n levels, each merging all n items, so it is O(n log n) on any list. It needs O(n) extra memory.

In a sentence

  • “Merge sort sorted the million-song library in about 20 million steps, whatever order the songs started in.”

Level: Journeyman · More Data Structures terms at this level

Updated