Data Structures and Algorithms · Searching and sorting

Divide-and-conquer sorting

Divide-and-conquer sorts, merge sort and quicksort, that beat O(n squared) by splitting the problem.

Also known as: merge sort, quicksort, O(n log n) sorting.

Start a lesson on Divide-and-conquer sorting

Learn first

• Elementary comparison sorts: The simple O(n squared) sorts, bubble, insertion, selection, that compare and swap pairs of elements.
• Recursion: A function solving a problem by calling itself on a smaller version of the same problem.

Leads to

• Divide and conquer: Splitting a problem into independent smaller copies of itself, solving each, then combining.

Related topics

• Heaps and priority queues: A tree-shaped structure that always keeps the smallest, or largest, element quick to find.
• Divide and conquer: Splitting a problem into independent smaller copies of itself, solving each, then combining.