🧮Merge Sort
Also known as Mergesort
A sort that splits the list in halves, sorts them, then merges them back.
Think of it like
Think of it like two piles of cards. Sort each pile, then join them in order.
Example
Lucy merge-sorts 8 numbers. They split into 8 single items, then merge into pairs, fours and one sorted list of 8.
Why it matters
Its speed never gets bad, and it keeps equal items in their first order. Many built-in sorts use its ideas.
Definition
Common mistake
Key takeaways
- 1Split, sort, merge. Again and again.
- 2Always O(n log n). No bad case.
- 3Needs extra memory. About the list's size.