Merge sort and quick sort are divide-and-conquer sorts averaging O(n log n). Merge sort splits in the middle and merges: O(n log n) always and stable, but it needs O(n) extra memory. Quick sort partitions around a pivot in place and is usually faster, but can take O(n²). Choose merge sort for stability or guaranteed time, quick sort for speed.
Below, both sort the same array step by step, so you can compare them move by move.
Both players sort 5, 2, 1, 4, 0, 6, 3, the quick sort topic's default array, from start to finish. Merge sort splits down to single values and compares only in the merges, moving values through an auxiliary array below. Quick sort compares from its first pass and swaps inside the array; each pivot it places turns green and is final. Here merge sort makes 14 comparisons, the most it can need for seven values, and quick sort 12.
Merge sort on 5, 2, 1, 4, 0, 6, 3
All steps as text
Sort the array using the Merge Sort algorithm.
Divide the array into two halves (subarrays). The left half contains indices [0, 3], and the right half contains indices [4, 6].
Focus on the left half [5, 2, 1, 4]. Process the right half [0, 6, 3] later.
Split into [5, 2] and [1, 4].
Examine the left subarray [5, 2]. Process the right subarray [1, 4] afterward.
Both subarrays contain single items, so they are already sorted. Merge them now.
Use the auxiliary array.
Mark the minimum value from the left subarray — currently 5.
Mark the minimum value from the right subarray — currently 2. Compare and merge these into the auxiliary array in sorted order.
Since 2 is smaller than 5, copy 2 first to the auxiliary array.
Copy 5 next.
Transfer values from the auxiliary array back to the original array.
Confirm that the merged part [2, 5] is sorted.
Focus on the right subarray [1, 4] and sort it in the same way.
Both subarrays contain single items, so they are already sorted. Merge them now.
Use the auxiliary array again for the merging process.
Mark the minimum value from the left subarray — currently 1.
Mark the minimum value from the right subarray — currently 4. Compare and merge these into the auxiliary array in sorted order.
Since 1 is smaller than 4, copy 1 first to the auxiliary array.
Copy 4 next.
Transfer values from the auxiliary array back to the original array.
Confirm that the merged part [1, 4] is sorted.
Revisit the subarray [2, 5, 1, 4].
Prepare to merge the sorted subarrays [2, 5] and [1, 4].
Use the auxiliary array again for the merging process.
Mark the minimum value from the left subarray — currently 2.
Mark the minimum value from the right subarray — currently 1. Compare and merge these into the auxiliary array in sorted order.
Since 1 is smaller than 2, copy 1 first to the auxiliary array.
Since 2 is smaller than 4, copy it to the auxiliary array.
Since 4 is smaller than 5, copy it to the auxiliary array.
Copy 5 next.
Transfer values from the auxiliary array back to the original array.
Confirm that the merged part [1, 2, 4, 5] is sorted.
Focus on the right subarray [0, 6, 3] and sort it in the same way.
Split into [0, 6] and [3].
Examine the left subarray [0, 6]. Process the right subarray [3] afterward.
Both subarrays contain single items, so they are already sorted. Merge them now.
Use the auxiliary array again for the merging process.
Mark the minimum value from the left subarray — currently 0.
Mark the minimum value from the right subarray — currently 6. Compare and merge these into the auxiliary array in sorted order.
Since 0 is smaller than 6, copy 0 first to the auxiliary array.
Copy 6 next.
Transfer values from the auxiliary array back to the original array.
Confirm that the merged part [0, 6] is sorted.
Revisit the subarray [0, 6, 3].
Prepare to merge the sorted subarrays [0, 6] and [3].
Use the auxiliary array again for the merging process.
Mark the minimum value from the left subarray — currently 0.
Mark the minimum value from the right subarray — currently 3. Compare and merge these into the auxiliary array in sorted order.
Since 0 is smaller than 3, copy 0 first to the auxiliary array.
Since 3 is smaller than 6, copy it to the auxiliary array.
Copy 6 next.
Transfer values from the auxiliary array back to the original array.
Confirm that the merged part [0, 3, 6] is sorted.
Check the whole array: [1, 2, 4, 5, 0, 3, 6].
Prepare to merge the sorted subarrays [1, 2, 4, 5] and [0, 3, 6].
Use the auxiliary array again for the merging process.
Mark the minimum value from the left subarray — currently 1.
Mark the minimum value from the right subarray — currently 0. Compare and merge these into the auxiliary array in sorted order.
Since 0 is smaller than 1, copy 0 first to the auxiliary array.
Since 1 is smaller than 3, copy it to the auxiliary array.
Since 2 is smaller than 3, copy it to the auxiliary array.
Since 3 is smaller than 4, copy it to the auxiliary array.
Since 4 is smaller than 6, copy it to the auxiliary array.
Since 5 is smaller than 6, copy it to the auxiliary array.
Finally, copy 6.
Transfer values from the auxiliary array back to the original array.
The array is now completely sorted.
Six merges made 14 comparisons, 20 copies into the auxiliary array and 20 back.
Quick sort sorts the same seven values with Lomuto's scheme: the last value of each segment is its pivot.
Quick sort on the same array
All steps as text
Sort the array using the Quick Sort algorithm.
Select the last element as the pivot.
Consider the element at index 0.
Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
Consider the element at index 1.
Since this element is less than the pivot and a marked element exists, swap them.
Increment the marker by one position after the swap.
Consider the element at index 2.
Since this element is less than the pivot and a marked element exists, swap them.
Increment the marker by one position after the swap.
Consider the element at index 3. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
Consider the element at index 4.
Since this element is less than the pivot and a marked element exists, swap them.
Increment the marker by one position after the swap.
Consider the element at index 5. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
After comparing all elements with the pivot, swap the pivot with the marked element.
Mark the pivot green, as it is now in its final position.
Focus on sorting the subarray obtained from the previous partitioning.
Select the last element as the pivot.
Consider the element at index 0.
Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
Consider the element at index 1. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
After comparing all elements with the pivot, swap the pivot with the marked element.
Mark the pivot green, as it is now in its final position.
Focus on sorting the subarray obtained from the previous partitioning.
Select the last element as the pivot.
Consider the element at index 1.
Since the element is less than the pivot and no element is marked yet, leave it in place.
Mark the pivot green, as it is now in its final position.
Focus on sorting the subarray obtained from the previous partitioning.
When a segment has only one element, treat it as sorted.
Focus on sorting the subarray obtained from the previous partitioning.
Select the last element as the pivot.
Consider the element at index 4.
Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
Consider the element at index 5. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
After comparing all elements with the pivot, swap the pivot with the marked element.
Mark the pivot green, as it is now in its final position.
Focus on sorting the subarray obtained from the previous partitioning.
Select the last element as the pivot.
Consider the element at index 5.
Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
After comparing all elements with the pivot, swap the pivot with the marked element.
Mark the pivot green, as it is now in its final position.
Focus on sorting the subarray obtained from the previous partitioning.
When a segment has only one element, treat it as sorted.
The array is fully sorted.
Five partitions made 12 comparisons with the pivot, three swaps and four pivot swaps, all inside the array itself.
Merge sort vs quick sort at a glance
Merge sort and quick sort both split an array into parts, sort the parts the same way and stop at parts of one value or none. They split differently, and that one choice decides their worst case, their memory and their stability.
Merge sort
Quick sort
Splits
In the middle, by position
Around a pivot, by value
Main work
Merging the sorted halves
Partitioning before the calls
Best and average time
The same: O(n log n)
Worst time
O(n log n)
O(n2)
Extra space
O(n): the auxiliary array
O(log n) stack on average, O(n) at worst
In place
No
Yes
Stable
Yes
No
Comparisons for seven values: best, average, worst
9, 12.7, 14
10, 13.5, 21
On the array above
14 comparisons, 40 copies
12 comparisons, 3 swaps, 4 pivot swaps
Linked lists
Well suited: merging relinks nodes
Poorly suited
Typical uses
Stable library sorts, external sorting
Fast in-memory sorting of arrays
The counts for seven values are over all orders of seven distinct values, quick sort with the app's Lomuto scheme.
Split by position or by value
Both are recursive. In pseudocode, with the names of the topic pages:
mergeSort(a, low, high)
if low >= high
return
mid = floor((low + high) / 2)
mergeSort(a, low, mid)
mergeSort(a, mid + 1, high)
merge(a, low, mid, high)
quickSort(a, low, high)
if low < high
p = partition(a, low, high)
quickSort(a, low, p - 1)
quickSort(a, p + 1, high)
Merge sort splits at mid without looking at a value, sorts both halves and only then works, in merge. Quick sort works first: partition moves the values smaller than the pivot before it and the rest after it, then the two calls sort the sides. The pivot at p is final and is left out of both calls, and nothing is merged afterward. The merge and partition functions are on the topic pages.
Merge sort splits by position: 8, 0, 5, 2, the merge sort page's example, becomes 8, 0 and 5, 2, whatever the values.Quick sort splits by value: the first partition of the array above puts 2, 1, 0 before the pivot 3 and 5, 6, 4 after it.
Worst case: why quick sort can take O(n2)
Merge sort always splits in the middle, so its recursion is about log2n levels deep and each level of merges handles all n values: O(n log n) whatever the input. Quick sort's split depends on the pivot. A pivot near the middle value halves the segment, as merge sort does. A pivot that is the smallest or largest value leaves one side empty, and if that happens every time, there are n levels: O(n2). With the last value as the pivot, input already sorted or reversed is exactly that case, and both are common.
A random pivot gives O(n log n) expected time on any input, and median-of-three, the middle one of the first, middle and last values, cuts the comparisons further. Neither guarantees O(n log n). Introsort does: it is quick sort that switches to heap sort when the recursion gets too deep.
Memory and stability
Merge sort copies each part into an auxiliary array and back, so it needs O(n) extra memory; merging in place is possible, but complex or slower. Quick sort only swaps inside the array. Its extra memory is the recursion stack, O(log n) with even splits; on sorted input the app's code nests one call per value, O(n). Recursing into the smaller side and looping on the larger keeps it O(log n).
Stable means that equal values keep their original order. Merge sort is stable because on a tie it takes the value from the left part, which came first. Quick sort is not: a swap can carry a value over an equal one. In 1, 2a, 2b the pivot is 2b, and its final swap with 2a gives 1, 2b, 2a. Stability matters when records are sorted by one key after another: sorted by name and then by city, each city's records stay in name order.
Merging [2a, 3] and [1, 2b]: on the tie the left 2 goes first, so 2a stays before 2b.Quick sort's pivot swap carries 2b over 2a: input already in order ends with the equal values reversed.
Which is faster in practice?
On arrays in memory quick sort is usually the faster, though it averages more comparisons for seven values, 13.5 against 12.7. Its inner loop is short, walks the array front to back and swaps within it. Merge sort copies each merged part into the auxiliary array and back: 40 copies for any seven values, while quick sort's run on the array above needs three swaps and four pivot swaps. On small arrays insertion sort runs faster than either, so library sorts hand small parts to it.
What the standard libraries use:
Library
Sort
Based on
Python list.sort(), sorted()
Timsort
Merge sort, stable
Java, arrays of objects
TimSort
Merge sort, stable
Java, arrays of int, long, float, double
Dual-pivot quicksort
Quick sort
C++ std::sort
Introsort (GCC, LLVM)
Quick sort
C++ std::stable_sort
Merge sort
Merge sort, stable
Only Java chooses by what it sorts: a merge sort for objects, whose equal values must keep their order, and a quick sort for primitive numbers, whose order among equals cannot be seen. Python uses Timsort for everything, and in C++ the caller picks std::sort or std::stable_sort.
When to use merge sort and when to use quick sort
Use merge sort when you need its guarantees:
Stability: records sorted by one key after another.
A guaranteed worst case: O(n log n) on any input, including input built to slow a sort down.
Linked lists: merging relinks nodes, so only the recursion stack is extra.
External sorting: data too large for memory is sorted in runs, which are then merged.
Parallel sorting: the two halves are independent.
Use quick sort when speed and memory matter more:
Large arrays in memory where the order of equal values does not matter.
Little spare memory: it sorts in place.
Numbers and other plain values, as Java's sorts of primitive arrays do.
Common mix-ups
Quick sort is always faster. Usually, not always: with the last value as the pivot, a sorted array is its worst case, 21 comparisons for seven values against merge sort's 11.
Quick sort needs no extra memory. It needs its recursion stack: O(log n) on average, O(n) at worst.
A sorted array is merge sort's best case. The basic version splits and merges the same way whatever the order. For seven values a sorted array makes 11 comparisons and a reversed one 9, the fewest.
Both are adaptive. Neither is in its basic form: input already in order sorts no faster. Timsort is, because it merges runs already in order.
Merge sort cannot sort in place. It can, but in-place merging is complex or slower, so the usual version takes O(n) extra memory.
Merge sort vs quick sort interview questions
Both are O(n log n) on average. Why is quick sort usually faster?
It works inside the array, with a short loop that walks it front to back and swaps within it. Merge sort copies each merged part into an auxiliary array and back, which costs time and memory even when the comparisons are fewer.
When would you choose merge sort over quick sort?
When equal values must keep their order, when O(n log n) must hold for every input, when the data is a linked list, and when it is too large for memory and has to be sorted in runs and merged.
What is quick sort's worst case, and how is it avoided?
Every pivot is the smallest or largest value of its segment, so each partition leaves one side empty: n levels and O(n2) time. With the last value as the pivot, sorted input does this. A random pivot or median-of-three makes it unlikely; introsort rules it out by switching to heap sort when the recursion gets too deep.
Why is merge sort stable and quick sort not?
Merge sort takes the left value on a tie, so of two equal values the earlier one stays first. Quick sort swaps values across the array, so one can jump over an equal value: in 1, 2a, 2b the pivot swap puts 2b before 2a.
How deep does the recursion go?
Merge sort's recursion is always about log2n levels deep, as it halves every part. Quick sort's depends on the pivots: about log2n with even splits, up to n when every partition leaves one side empty. Recursing into the smaller side first and looping on the larger keeps quick sort's stack O(log n) in every case.
Related topics
Merge Sort: the merge, the recursion tree and stability in detail.
Quick Sort: Lomuto and Hoare partitions, pivot choice and the worst case.
Heap Sort: the third O(n log n) sort, in place and guaranteed.
Insertion Sort: faster on small parts, so library sorts hand them to it.
In VisiGrab, merge sort and quick sort each sort the default, a random or your own array of seven values, step by step, forward and back.
The same array for both
Random picks seven distinct values from 0 to 19, and Custom takes your own from 0 to 99, equal ones included. The last random or custom array comes back in merge sort, quick sort, bubble, selection and insertion sort.
Every step, forward and back
Merge sort shows every split, min label and copy, 75 steps for any seven values; quick sort every pivot, comparison, swap and green mark.
Hoare's partition too
A panel switches quick sort from Lomuto's scheme to Hoare's: two markers scan from both ends, swap and cross, in 59 steps on the default array.
Theory for both
Merge sort's info dialog ends on external sorting. Quick sort's has two tabs: divide and conquer and the three cases, then the partition schemes and pivot selection.
Python, Java and C++
Both sorts in all three languages, quick sort with both partition schemes, linked to the full source on GitHub.
Two quizzes
Eight questions on each sort, with an explanation for every answer.
// sort your own
Split or partition, on your own array.
Download VisiGrab to step through merge sort and quick sort on the same seven values, yours or random, forward and back.