Merge Sort

Table of Contents +

Say you have a big messy list of numbers and you need them sorted. Bubble sort and selection sort work, sure. But they get slow when the list grows large. So we need a smarter idea. Merge sort is that idea. It sorts even huge lists fast. And it does it with a trick called divide and conquer.

Divide and conquer means you break a big problem into smaller pieces. You solve each small piece. Then you join the answers back together. That is the whole heart of merge sort. So let us see how it actually works.

🧠 The Big Idea

Think about sorting a stack of exam papers by marks. Doing the whole stack at once feels hard, right? So you split the stack in half. You give one half to a friend. You keep the other half. Each of you sorts your smaller pile. Then you both sit together and combine the two sorted piles into one final sorted stack.

That last step, combining two already-sorted piles, is easy. You just keep comparing the top paper of each pile and pick the smaller one.

Merge sort does exactly this:

  • Split the array into two halves.
  • Sort the left half (the same way, by splitting it again).
  • Sort the right half (same way).
  • Merge the two sorted halves into one sorted array.

The splitting keeps going until each piece has only one element. A single element is already sorted by itself. Then the merging starts and builds everything back up, in order.

🪓 The Splitting Part

We keep cutting the array in half until we can not cut anymore. Here is an array of size 8 getting split down to single elements.

38 27 43 3 9 82 10 1

38 27 43 3

9 82 10 1

38 27

43 3

9 82

10 1

38

27

43

3

9

82

10

1

See how each box breaks into two smaller boxes? At the bottom every box holds just one number. Now there is nothing left to split. So we turn around and start merging.

🔗 The Merge Step (the important one)

This is the part that really matters, so go slow here. The merge step takes two sorted halves and joins them into one sorted array.

The thing is, both halves are already sorted. So you only ever need to look at the front of each half. You compare the two front elements. You pick the smaller one. You put it in the result. Then you move forward in that half. You repeat until one half runs out. Then you copy whatever is left from the other half.

Here is the merge in points:

  • Look at the front element of the left half and the front element of the right half.
  • Take the smaller one and put it into the result array.
  • Move forward by one in the half you just took from.
  • Keep going until one half is empty.
  • Copy any leftover elements from the other half straight into the result.

Let us merge two sorted halves, [27, 38] and [3, 43], so you can see it.

Left: 27 38

Result: 3 27 38 43

Right: 3 43

Let us walk it slowly. Front of left is 27. Front of right is 3. 3 is smaller, so 3 goes first. Now look again. Left still has 27. Right now has 43. 27 is smaller, so 27 goes next. Then 38 is smaller than 43, so 38 goes. Now the left half is empty. So we just copy the leftover 43. The final result is [3, 27, 38, 43]. Sorted.

🧱 Steps to Merge Sort an Array

Here is the full plan before we write any code.

  1. If the array has one element or is empty, it is already sorted, so just return.
  2. Find the middle index of the array.
  3. Recursively merge sort the left half, from start to middle.
  4. Recursively merge sort the right half, from middle to end.
  5. Merge the two sorted halves back together using the merge step.
  6. The array is now fully sorted.

💻 Merge Sort in Code

Now let us put it together. Each version below has a merge helper that joins two sorted halves, and a mergeSort function that splits and calls itself. We sort the same array [38, 27, 43, 3, 9, 82, 10, 1] in every language.

merge_sort.py
# Merge two sorted lists into one sorted list
def merge(left, right):
    result = []
    i = j = 0
    # Pick the smaller front element each time
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Copy whatever is left over
    result.extend(left[i:])
    result.extend(right[j:])
    return result




def merge_sort(arr):
    if len(arr) <= 1:        # one element, already sorted
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])  # sort right half
    return merge(left, right)      # merge them




numbers = [38, 27, 43, 3, 9, 82, 10, 1]
print(merge_sort(numbers))

The output of the above code will be:

Output
[1, 3, 9, 10, 27, 38, 43, 82]

Tip

The merge helper is the real engine here. The <= check (instead of <) is what keeps merge sort stable. Stable means two equal values stay in the same order they were in before sorting. That matters when you sort records by one field but want ties to keep their old order.

⏱️ How Fast Is It?

Merge sort splits the array into halves again and again. Splitting in half repeatedly gives you about log n levels. At each level you do n work to merge everything. So the total work is n multiplied by log n, which we write as O(n log n).

And here is the nice part. It does not matter if the array is already sorted, reversed, or random. Merge sort always does the same amount of work. So the best, average, and worst case are all O(n log n).

The trade-off is space. Merge sort needs an extra array to hold elements while merging. That extra room is about the size of the input, so the space cost is O(n).

Note

Merge sort always runs in O(n log n) time, even in the worst case. That steady, predictable speed is its biggest strength over quick sort, which can slow down to O(n^2) on bad inputs.

Here is the full picture in one table.

Case Time Complexity Space Complexity
Best (already sorted) O(n log n) O(n)
Average (random order) O(n log n) O(n)
Worst (reverse order) O(n log n) O(n)

⚠️ Common Mistakes

A few things trip people up the first time, so watch for these.

  • Forgetting the base case. If you do not stop when the array has one element, the recursion never ends and the program crashes.
  • Computing the middle wrong. Use left + (right - left) / 2, not (left + right) / 2, since the second one can overflow for very large indexes in C, C++, and Java.
  • Forgetting to copy the leftovers. After one half empties, the other half still has sorted elements waiting. If you skip copying them, you lose data.
  • Thinking it sorts without extra memory. Merge sort needs that extra array. If memory is tight, that is something to keep in mind.

🧩 What You’ve Learned

  • ✅ Merge sort uses divide and conquer: split the array in half, sort each half, then merge.
  • ✅ The split keeps going until each piece has a single element, which is already sorted.
  • ✅ The merge step compares the front of each sorted half and takes the smaller one each time.
  • ✅ You wrote merge sort in C, C++, Java, Python, and JavaScript with a merge helper.
  • ✅ Its time is always O(n log n), it uses O(n) extra space, and it is stable.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What strategy does merge sort use?

    Why: Merge sort splits the problem into halves, sorts each, then combines them, which is divide and conquer.

  2. 2

    In the merge step, how do you choose the next element for the result?

    Why: Both halves are already sorted, so you compare their front elements and take the smaller one.

  3. 3

    What is the time complexity of merge sort in the worst case?

    Why: Merge sort always does the same work regardless of input, so even the worst case is O(n log n).

  4. 4

    Why is merge sort called stable?

    Why: Using <= when merging keeps equal values in the order they appeared, which is what stable means.

Score: 0 / 4

🚀 What’s Next?

Previous Insertion Sort Next Quick Sort

Share & Connect

Share on LinkedIn