Python Program for Merge Sort with Example and Explanation

A Python program for merge sort uses a merge_sort function that splits the list into halves recursively and merges sorted halves using a merge helper function, like 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).

Examples

Input[3, 1, 4, 2]

Output[1, 2, 3, 4]

Input[10, 5, 2, 3, 7, 6]

Output[2, 3, 5, 6, 7, 10]

Input[]

Output[]

How to Think About It

To sort a list using merge sort, think of breaking the list into smaller parts until each part has one or no elements. Then, combine these small parts by comparing their elements in order, building up a sorted list step by step. This uses the idea of dividing the problem into smaller pieces and then merging them back in order.

Algorithm

1

Check if the list has one or no elements; if yes, return it as it is already sorted.

2

Split the list into two halves.

3

Recursively apply merge sort to each half.

4

Merge the two sorted halves by comparing elements one by one.

5

Return the merged sorted list.

Code

python

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

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)

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

Output

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

Dry Run

Let's trace the list [3, 1, 4, 2] through the merge sort code.

1

Split list

Split [3, 1, 4, 2] into [3, 1] and [4, 2]

2

Sort left half

Split [3, 1] into [3] and [1], both single elements, so return as is

3

Merge left half

Compare 3 and 1, merge into [1, 3]

4

Sort right half

Split [4, 2] into [4] and [2], both single elements, so return as is

5

Merge right half

Compare 4 and 2, merge into [2, 4]

6

Merge both halves

Compare [1, 3] and [2, 4], merge into [1, 2, 3, 4]

Step	List State
Initial	[3, 1, 4, 2]
Split	[3, 1] and [4, 2]
Sort Left	[3] and [1]
Merge Left	[1, 3]
Sort Right	[4] and [2]
Merge Right	[2, 4]
Final Merge	[1, 2, 3, 4]

Why This Works

Step 1: Divide the list

The code splits the list into two halves recursively until each sublist has one or zero elements, which are naturally sorted.

Step 2: Merge sorted halves

It then merges two sorted lists by comparing their first elements and building a new sorted list step by step.

Step 3: Combine results

This merging continues up the recursion chain until the entire list is merged back into a fully sorted list.

Alternative Approaches

In-place merge sort

python

def merge_sort_inplace(arr, start=0, end=None):
    if end is None:
        end = len(arr)
    if end - start > 1:
        mid = (start + end) // 2
        merge_sort_inplace(arr, start, mid)
        merge_sort_inplace(arr, mid, end)
        left = arr[start:mid]
        right = arr[mid:end]
        i = j = 0
        k = start
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

arr = [5, 3, 8, 6, 2]
merge_sort_inplace(arr)
print(arr)

This version sorts the list in place without creating many new lists, saving memory but making the code a bit more complex.

Bottom-up merge sort

python

def merge_sort_bottom_up(arr):
    width = 1
    n = len(arr)
    while width < n:
        for i in range(0, n, 2*width):
            left = arr[i:i+width]
            right = arr[i+width:i+2*width]
            arr[i:i+2*width] = merge(left, right)
        width *= 2
    return arr

arr = [7, 2, 5, 3, 9]
print(merge_sort_bottom_up(arr))

This approach sorts by merging pairs of sublists iteratively, avoiding recursion but requiring careful indexing.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the list into halves recursively (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time.

Space Complexity

It requires extra space to hold temporary lists during merging, so space complexity is O(n). In-place variants can reduce this.

Which Approach is Fastest?

Recursive merge sort is simple and fast for most cases; in-place and bottom-up variants save memory but add complexity.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Simplicity and clarity
In-place Merge Sort	O(n log n)	O(1) to O(n)	Memory-sensitive environments
Bottom-up Merge Sort	O(n log n)	O(n)	Avoiding recursion overhead