Merge Sort

Algorithms

Merge sort is a divide-and-conquer algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves.

Algorithm

The merge sort algorithm follows these steps:

Divide the array into two halves
Recursively sort both halves
Merge the two sorted halves

Time Complexity

Merge sort has a time complexity of $O (n lo g n)$ in all cases (best, average, and worst), where $n$ is the number of elements.

Space Complexity

The space complexity is $O (n)$ due to the temporary arrays used during merging.

Implementation

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle point
        mid = len(arr) // 2
        # Divide the array into two halves
        L = arr[:mid]
        R = arr[mid:]

        # Recursively sort both halves
        merge_sort(L)
        merge_sort(R)

        # Merge the sorted halves
        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr

# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

Trace it by hand

ProblemTrace the merge step

The recursive merge-sort algorithm has split an array into two sorted halves: [2, 5, 8] and [1, 4, 9]. Trace the merge step one comparison at a time. Each step compares the front element of each half and emits the smaller. What's the resulting merged array, and what comparison sequence produced it?