4.2. Merge Sort

Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. Merge sort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined.

It is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

The merge sort algorithm uses the merge procedure detailed below to combine two sorted sub-arrays into one sorted array.

merge: Merge two given sorted lists into one sorted list

---

Given two sorted linked lists list1 and list2, merge the two lists into one sorted list. The merged sorted list should be made by splicing together the numbers of the given two lists.

For example,

• Input: list1 = [1, 3, 5], list2 = [2,4,6] Output: [1,2, 3, 4, 5, 6]

• Input: list1 = [1, 1, 2], list2 = [0, 1, 3] Output: [0, 1, 1, 1, 2, 3]

• Input: list1 = [4], list2 = [0] Output: [0, 4]

Note that the merge procedure is of linear time complexity and has space complexity of O(n) since it creates a new list of size n to store the merged list.

def merge(list1, list2):
  """ Merge two given sorted lists into one sorted list """
  i, j = 0, 0
  merged = []

  # Merge the two lists until one of them is exhausted
  while i < len(list1) and j < len(list2):
    if list1[i] < list2[j]:
      merged.append(list1[i])
      i = i+1
    else:
      merged.append(list2[j])
      j = j+1

  # Add the remaining elements of list1
  while i < len(list1):
    merged.append(list1[i])
    i = i + 1

  # Add the remaining elements of list2
  while j < len(list2):
    merged.append(list2[j])
    j = j + 1

  return merged

assert merge([1, 3, 5], [2, 4, 6])    == [1, 2, 3, 4, 5, 6],    "Test case 1 failed"
assert merge([-1, 10, 15], [2, 4, 6]) == [-1, 2, 4, 6, 10, 15], "Test case 2 failed"
assert merge([1, 3, 3], [3, 3, 5, 7]) == [1, 3, 3, 3, 3, 5, 7], "Test case 3 failed"
assert merge([], [1, 2, 3])           == [1, 2, 3],             "Test case 4 failed"
assert merge([2], [1])                == [1, 2],                "Test case 5 failed"

print("All test cases passed successfully")

4.2.1. Steps

The merge sort algorithm closely follows the divide and conquer paradigm. Intuitively, it operates as follows:

1. Divide: Convert the input unsorted n-element list into a list of n sublists each of length 1.

2. Conquer: Repeatedly, ‘merge’ adjacent pairs of sublists until there is only one sorted list remaining.

Fig. 4.5 Merge sort algorithm example.

Note that the merge procedure expects sorted lists as inputs and at the first step, input lists of length 1 are trivially sorted.

4.2.2. Pseudocode

Algorithm 4.2 (Merge Sort Algorithm)

Inputs Given a list of numbers \(L\) of length \(n\)

Output A sorted list \(L\) of numbers of length \(n\)

\(L^{\prime}\) \(\leftarrow\) [[\(x\)] for \(x \in L\)]

\(\text{while}~~length(L^{\prime}) > 1\)
  \(result \leftarrow [~]\)
  \(i \leftarrow 0\)
  \(\text{while}~~i < length(L^{\prime})\)
      \( merged~~\leftarrow~~merge(L^{\prime}_{~i}~~,~~L^{\prime}_{~i+1}) \)
      Add merged to result
      \(i \leftarrow i + 2\)
  \( L^{\prime} \leftarrow\) result
end while

4.2.3. Implementation

def merge_sort(data):
  result = []

  for x in data:
    result.append([x])

  while len(result) > 1:
    newlist = []
    i = 0
    while i <= len(result) - 1:
      if i+1 == len(result): 
        newlist.append(result[i])
      else:
        list1 = result[i]
        list2 = result[i+1]
        merged = merge(list1, list2)
        newlist.append(merged)
      i = i + 2

    result = newlist

  return result[0]

assert merge_sort([1, 3, 5, 2, 4, 6]) == [1, 2, 3, 4, 5, 6], "Test case 1 failed"
assert merge_sort([1, 1, 2, 2, 0, 0]) == [0, 0, 1, 1, 2, 2], "Test case 2 failed"
assert merge_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5], "Test case 3 failed"
assert merge_sort([1]) == [1], "Test case 4 failed"
assert merge_sort([2, 1]) == [1, 2], "Test case 5 failed"

4.2.4. Complexity

The merge sort algorithm starts with \(n\) sublists of size 1 and ends with a 1 sorted list of size \(n\).

In going from \(n\) sublists to 1 sublist, it repeatedly merges two sorted lists into one sorted list. That means, at each step the number of sorted lists is halved!

Therefore, the number of steps required to reach a single sorted list is \(\log_2 n\) or \(\log n\), if we ignore the base.

The merge procedure scales linearly with the size of the input lists. Therefore, the time complexity of merge sort is \(O(n\log n)\).

Each pass requires \(O(n)\) comparisons for merging, so the overall complexity is \(O(n\log n)\).

The space complexity of merge sort is \(O(n)\). The merge function requires an auxiliary array of size \(n\).

4.2.5. Recursive Implementation

For recursive implementation, go to Section 5.5.2.