Quick Sort vs Merge Sort
Both are O(n log n) divide-and-conquer sorts, but they make very different tradeoffs between speed, memory, and predictability.
An efficient, in-place, comparison-based sorting algorithm. It applies the divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
When to use it
Use Quick Sort when you're sorting in-place with limited memory and average-case performance matters more than worst-case guarantees — it's typically faster in practice due to better cache locality and lower constant factors.
An efficient, stable, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. The algorithm splits the array into two halves, recursively sorts them, and then merges the two sorted halves.
When to use it
Use Merge Sort when you need a stable sort, predictable O(n log n) performance in every case, or when sorting linked lists or external data that doesn't fit in memory.
Key Differences
- Quick Sort sorts in-place (O(log n) space for recursion); Merge Sort needs O(n) auxiliary space.
- Quick Sort's worst case is O(n²) on adversarial or already-sorted input with a poor pivot; Merge Sort is always O(n log n).
- Merge Sort is stable (equal elements keep their relative order); Quick Sort is not stable by default.
- Quick Sort generally has better real-world performance due to cache-friendly in-place partitioning.
For general in-memory sorting where average speed matters, Quick Sort usually wins. For guaranteed worst-case performance or stability, reach for Merge Sort.