Merge Sort Algorithm in DSA Python

Mental Model

Split the list into smaller parts, sort each part, then join them back together in order.

Analogy: Imagine sorting a big pile of cards by first dividing them into small piles, sorting each small pile, then carefully combining the piles back into one sorted stack.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split again:
[38] [27, 43]   [3, 9] [82, 10]

Sorted small parts:
[27, 38, 43]   [3, 9] [10, 82]

Merged sorted list:
[3, 9, 10, 27, 38, 43, 82]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split list into two halves

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

Why: Divide the problem into smaller parts to sort them easily

Step 2: Split left half into smaller parts

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

Why: Keep splitting until each part has one element

Step 3: Split right half into smaller parts

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

Why: Keep splitting until each part has one element

Step 4: Sort and merge [27] and [43]

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

Why: Merge two single-element lists into sorted list

Step 5: Sort and merge [3] and [9]

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

Why: Merge two single-element lists into sorted list

Step 6: Sort and merge [82] and [10]

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

Why: Merge two single-element lists into sorted list

Step 7: Merge [3, 9] and [10, 82]

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

Why: Merge two sorted lists into one sorted list

Step 8: Merge [38] and [27, 43]

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

Why: Merge two sorted lists into one sorted list

Step 9: Merge [27, 38, 43] and [3, 9, 10, 82]

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

Why: Merge two sorted lists into the final sorted list

Result:

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

Annotated Code

DSA Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# Driver code
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

if len(arr) <= 1: return arr

stop splitting when list has one or zero elements

mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:])

split list into two halves and sort each half recursively

while i < len(left) and j < len(right):

merge two sorted halves by comparing elements

if left[i] < right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1

append smaller element and move pointer forward

merged.extend(left[i:]) merged.extend(right[j:])

append remaining elements after one half is exhausted

return merged

return merged sorted list

Output

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

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes O(n) at each level

Space: O(n) because extra space is needed to hold merged lists during the process

vs Alternative: Compared to simple sorting like bubble sort O(n^2), merge sort is much faster for large lists but uses extra memory

Edge Cases

empty list

returns empty list immediately without error

DSA Python

if len(arr) <= 1:
    return arr

list with one element

returns the same single-element list immediately

DSA Python

if len(arr) <= 1:
    return arr

list with duplicate elements

duplicates are kept and sorted correctly

DSA Python

if left[i] <= right[j]:
    merged.append(left[i])
    i += 1
else:
    merged.append(right[j])
    j += 1

When to Use This Pattern

When you see a problem asking to sort or order data efficiently, especially large lists, reach for merge sort because it splits and merges to keep sorting fast.

Common Mistakes

Mistake: Not handling the base case of list length 1 or 0, causing infinite recursion
Fix: Add a condition to return the list immediately if its length is 1 or less

Mistake: Merging without comparing elements properly, leading to unsorted output
Fix: Use two pointers to compare and append the smaller element step by step

Mistake: Forgetting to append remaining elements after one half is exhausted
Fix: Extend the merged list with leftover elements from either half after the main loop

Summary

It sorts a list by splitting it into smaller parts, sorting those, and merging them back together.

Use it when you need a reliable, efficient sorting method for medium to large lists.

The key insight is breaking the problem into smaller sorted pieces and merging them carefully.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Swap adjacent elements repeatedly until sorted

B. Divide the list into halves, sort each half, then merge them

C. Pick the smallest element and move it to the front repeatedly

D. Build a sorted list by inserting elements one by one

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to make sorting easier.

2. Step 2: Merge sorted halves

   After sorting each half, it combines them to form a fully sorted list.

3. Final Answer:

   Divide the list into halves, sort each half, then merge them -> Option B

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking it swaps elements directly without splitting
• Assuming it sorts in one pass

2. Which of the following is the correct way to split a list arr into two halves in Python for merge sort?

easy

A. left = arr[:len(arr)//2+1]; right = arr[len(arr)//2:]

B. left = arr[1:len(arr)//2]; right = arr[len(arr)//2+1:]

C. left = arr[:len(arr)//2]; right = arr[len(arr)//2:]

D. left = arr[:len(arr)/2]; right = arr[len(arr)/2:]

Solution

1. Step 1: Use integer division for slicing

   Python list slicing requires integer indices; len(arr)//2 gives an integer midpoint.

2. Step 2: Slice correctly for left and right halves

   Left half is from start to midpoint (exclusive), right half from midpoint to end.

3. Final Answer:

   left = arr[:len(arr)//2]; right = arr[len(arr)//2:] -> Option C

4. Quick Check:

   Integer division and slicing = left = arr[:len(arr)//2]; right = arr[len(arr)//2:] [OK]

Hint: Use // for integer division in slicing [OK]

Common Mistakes:

• Using single slash / causing float index error
• Incorrect slice ranges skipping elements
• Adding +1 unnecessarily in slicing

3. What will be the output of the following code snippet?

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([4, 1, 3, 2]))

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Recursively split and sort the list

   The list [4,1,3,2] is split into [4,1] and [3,2], then further until single elements.

2. Step 2: Merge sorted halves step-by-step

   Merge [4] and [1] to get [1,4], merge [3] and [2] to get [2,3], then merge [1,4] and [2,3] to get [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Sorted list = [1, 2, 3, 4] [OK]

Hint: Trace splits and merges carefully [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Not extending remaining elements after main loop
• Mixing up indices i and j

4. Identify the error in this merge function used in merge sort:

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) or j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result

medium

A. Using 'or' instead of 'and' in while condition causes index errors

B. Missing initialization of result list

C. Appending elements without comparing

D. Not returning the merged list

Solution

1. Step 1: Analyze the while loop condition

   Using 'or' means loop continues even if one list is exhausted, causing index out of range errors.

2. Step 2: Correct condition and handle leftovers

   The condition should be 'and' to compare elements safely, then extend remaining elements after loop.

3. Final Answer:

   Using 'or' instead of 'and' in while condition causes index errors -> Option A

4. Quick Check:

   While condition must be 'and' to avoid errors [OK]

Hint: Use 'and' in loop to avoid index errors [OK]

Common Mistakes:

• Using 'or' causing index out of range
• Not extending leftover elements after loop
• Forgetting to increment indices properly

5. You want to sort a list of tuples [(3, 'c'), (1, 'a'), (2, 'b')] by the first element using merge sort. Which modification is needed in the merge function's comparison?

hard

A. Compare using if left[i][1] < right[j][1]:

B. Use if left[i] < right[j]: without change

C. Convert tuples to strings before comparing

D. Change comparison to if left[i][0] < right[j][0]:

Solution

1. Step 1: Understand tuple comparison

   Tuples compare element-wise, but to sort by first element explicitly, compare left[i][0] and right[j][0].

2. Step 2: Modify merge comparison accordingly

   Change the if condition in merge to compare the first elements of tuples for correct sorting.

3. Final Answer:

   Change comparison to if left[i][0] < right[j][0]: -> Option D

4. Quick Check:

   Compare tuple first elements for sorting [OK]

Hint: Compare tuple elements explicitly by index [OK]

Common Mistakes:

• Comparing whole tuples without index may work but is unclear
• Comparing second element instead of first
• Converting tuples to strings unnecessarily