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