Merge Sort and Quick Sort
Divide-and-conquer sorts are far faster for large data.
About this topic
Merge sort and quicksort are fast sorting algorithms that use the divide and conquer approach. Merge sort splits the list in half repeatedly until each piece has one item, then merges sorted pieces back together by repeatedly taking the smaller front item. Quicksort picks a pivot, partitions the list into items smaller and larger than the pivot, then sorts each part recursively.
Both average O(n log n) time, far better than O(n squared) for large lists: sorting a million items takes roughly 20 million steps instead of a trillion. Merge sort guarantees n log n even in the worst case and is stable but needs extra memory. Quicksort works in place and is usually very fast in practice, but a poor pivot choice, such as always the first item in sorted data, can degrade it to O(n squared).
Standard libraries in Python, Java and other languages use hybrids of these ideas. For example, merging [2, 5] and [3, 4] gives [2, 3, 4, 5]. A common misconception is that quicksort is always fastest. Choosing a random or middle pivot helps. Both rely heavily on recursion, so understanding base cases is essential.
Key ideas
- O(n log n)
- Merge sort splits and merges
- Quick sort partitions around a pivot
Quick check
Use cases: where Merge Sort and Quick Sort helps
- Homework: review the key idea behind Merge Sort and Quick Sort before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Merge Sort and Quick Sort without notes.
- Visual learning: play with the interactive lab to see how Merge Sort and Quick Sort changes when you adjust its inputs.
- Teaching a friend: explain Merge Sort and Quick Sort in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Merge Sort and Quick Sort?
Divide-and-conquer sorts are far faster for large data.
What will I learn in Merge Sort and Quick Sort?
O(n log n). Merge sort splits and merges. Quick sort partitions around a pivot.
Is Merge Sort and Quick Sort part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Merge Sort and Quick Sort lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Merge Sort and Quick Sort?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.