Merge Sort¶

1   n1 = q - p + 1
2   n2 = r - q
3   let L[1..n1+1] and R[1..n2+1] be new arrays
4   for i = 1 to n1
5       L[i] = A[p+i-1]
6   for j = 1 to n2
7       R[j] = A[q+j]
8   L[n1 + 1] = Inf
9   R[n2 + 1] = Inf
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j]
14          A[k] = L[i]
15          i = i + 1
16      else
17          A[k] = R[j]
18          j = j + 1

1   if p < r
2       q = [p + r]/2
3       MERGE-SORT(A, p, q)
4       MERGE-SORT(A, q+1, r)
5       MERGE(A, p, q, r)

import math

def merge(A, p, q, r):
    """Merges sorted subarrays

    This procedure assumes that the subarrays A[p..q] and A[q+1..r] are sorted. 
    Merges the subarrays to form single sorted subarray A[p..r]

    Args:
        A: Array to be sorted
        p: Index of start of first subarray
        q: Index of end of first subarray
        r: Index of end of second subarray
    """
    n1 = q - p + 1 # length of subarray A[p..q]
    n2 = r - q     # length of subarray A[q+1..r]

    # Initialize arrays L and R
    L = [A[p + i]     for i in range(0, n1)]
    L.append(math.inf)

    R = [A[q + j + 1] for j in range(0, n2)]
    R.append(math.inf)

    # Construct A[p..r] from L and R in sorted order
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A

def merge_sort(A):
    """Sorts the array `A` in ascending order using `Merge sort` algorithm

    Args:
        A: Array of numbers to be sorted

    Returns:
        Array of numbers in sorted, ascending order
    """

    # Recursively callable method
    def merge_sort_r(A, p, r):
        if p < r:
            q = (p + r) // 2 
            merge_sort_r(A, p    , q) # Sort first half
            merge_sort_r(A, q + 1, r) # Sort second half
            merge(A, p, q, r)         # Merge first and second half
    merge_sort_r(A, 0, len(A) - 1)

    return A

tests = [
    [31, 41, 59, 26, 41, 58],
    [],
    [40, 20],
    [1],
    [10, 9, 8, 7],
    [7, 8, 9, 10]
]

for input_array in tests:
    print(f'Input: {input_array}')
    output_array = merge_sort(input_array)
    print(f'Sorted: {output_array}\n')

Input: [31, 41, 59, 26, 41, 58]
Sorted: [26, 31, 41, 41, 58, 59]

Input: []
Sorted: []

Input: [40, 20]
Sorted: [20, 40]

Input: [1]
Sorted: [1]

Input: [10, 9, 8, 7]
Sorted: [7, 8, 9, 10]

Input: [7, 8, 9, 10]
Sorted: [7, 8, 9, 10]