Merge Sort

Definition

Merge sort is an efficient, comparison-based sorting algorithm known for its stability. It organizes the data by dividing the list into smaller subarrays, sorting them, and then merging them back together into a fully sorted array.

Properties

Merge sort follows the divide and conquer paradigm:

Time Complexity: In the best, worst, and average cases, the algorithm runs in

Θ(n \log n)

Space Complexity: Typically, merge sort requires

Θ(n)

extra space. Although the algorithm can be implemented with only

Θ(1)

auxiliary space, it is common and simpler to use an auxiliary array of the same length as the input.

Stability: Merge sort maintains the relative order of equal elements. This is achieved during the merging step by ensuring that when two elements are equal, the element from the first subarray is chosen first.

The Process

The key idea in merge sort is to break the problem into smaller parts and then combine the solutions. The process consists of two main steps: merging and dividing.

Merging

At the heart of merge sort is the merging process, which combines two sorted arrays into one sorted array. Suppose you have two sorted arrays, say "a" and "b". The algorithm compares the current elements of each array and appends the smaller one to a new array "c". This continues until one of the arrays is exhausted, after which the remaining elements from the other array are simply appended.

To ensure stability (preserving the order of equal elements), when the first element of the first array is equal to that of the second array, the element from the first array is chosen.

Implementation

Below is a Python implementation of the merging process:

def merge(a, b):
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        # Check b[j] < a[i] first to guarantee stability.
        if b[j] < a[i]:
            c.append(b[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
    # One of the arrays is exhausted; append the remaining elements.
    c.extend(a[i:])
    c.extend(b[j:])
    return c

Recursive Merge Sort (Divide and Conquer Approach)

Merge sort works by recursively splitting the array into halves until each subarray contains only one element (which is inherently sorted). Then, the merge process is applied to combine these sorted subarrays step by step until the entire array is sorted.

When dividing the array, it is common to split it as evenly as possible. For an array with indices from l (inclusive) to r (exclusive), the midpoint can be determined as:

$\text{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor.$

Below is a Python version of the recursive merge sort:

def merge_sort_recursive(a, left, right):
    # If the segment length is 1 or less, it's already sorted.
    if right - left <= 1:
        return
    mid = (left + right) // 2
    merge_sort_recursive(a, left, mid)
    merge_sort_recursive(a, mid, right)
    # Merge the sorted halves
    a[left:right] = merge(a[left:mid], a[mid:right])

To sort an entire list a, call the function with left = 0 and right = len(a).

Iterative (Bottom-Up) Merge Sort

Another way to implement merge sort is by using an iterative approach, often referred to as the bottom-up method. This method initially treats each element as a sorted segment of length 1. It then iterates through the list, merging adjacent segments. After the first pass, you obtain sorted segments of length up to 2; a second pass merges these to get segments of length up to 4, and so on. This process continues until the whole list is merged and sorted.

Keep in mind that if the number of elements is not a power of two, the last segment in a pass might be shorter than the others.

Here is a Python implementation of the iterative merge sort:

def merge_sort_iterative(a):
    n = len(a)
    seg = 1
    # Increase the segment size by doubling each time.
    while seg < n:
        for start in range(0, n - seg, seg * 2):
            mid = start + seg
            end = min(start + seg * 2, n)  # Ensure not to exceed list length
            a[start:end] = merge(a[start:mid], a[mid:end])
        seg *= 2

Inversion Count

An inversion in an array is a pair of indices (i, j) such that $i < j$ and $a_i > a_j$ . A fully sorted array contains no inversions.

Merge sort can be augmented to count inversions efficiently during the merge process. When merging, every time the element from the second subarray is chosen (i.e., when $b[j] < a[i]$ ), the number of remaining elements in the first subarray is added to the count of inversions. Thus, the inversion count during merge sort runs in

Θ(n \log n)

Alternative methods for counting inversions include using Binary Indexed Trees (Fenwick Trees) or Segment Trees, both offering comparable efficiency.

This guide provides an introduction to merge sort, covering both its recursive and iterative implementations and offering insights into how the merging process can also solve related problems such as inversion counting. Happy coding!

Insertion Sort QuickSort