merge sort
A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
In more detail
Its recurrence T(n) = 2T(n/2) + n gives O(n log n) in every case, not just on average. It is stable but needs O(n) extra memory for merging. The merge step, repeatedly taking the smaller front item of two sorted lists, is also the heart of external sorting.
Related terms
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
- sorted merge — Combining two or more already sorted sequences into one sorted sequence by repeatedly taking the smallest front item.
- stable sort — A sort that keeps items with equal keys in the same relative order they had before sorting.
- recurrence relation — An equation that defines an algorithm's cost on input size n in terms of its cost on smaller inputs, such as T(n) = 2T(n/2) + n.
- log-linear time — Work that grows as n times log n, written O(n log n), the typical cost of efficient comparison sorting.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers