Lines 6–7 define the merge_sort function. Line 7 calls function sort_array to initiate the recursive algorithm, passing 0 and len(data) - 1 as the low and high indices of the array to be sorted. These values tell function sort_array to operate on the entire array.

1  # mergesort.py
2  """Sorting an array with merge sort."""
3  import numpy as np
4
5  # calls recursive sort_array method to begin merge sorting
6  def merge_sort(data):
7      sort_array(data, 0, len(data) - 1)
8

Function sort_array (lines 9–26) performs the recursive merge sort algorithm. Line 12 tests the base case. If the size of the array is 1, the array is already sorted, so the function returns immediately. If the size of the array is greater than 1, the function splits the array in two, recursively calls function sort_array to sort the two subarrays, then merges them. Line 22 recursively calls function sort_array on the first half of the array, and line 23 recursively calls function sort_array on the second half. When these two function calls return, each half of the array has been sorted. Line 26 calls function merge (lines 29–61) with the indices for the two halves of the array to combine the two sorted arrays into one larger sorted array.

 9  def sort_array(data, low, high):
10      """Split data, sort subarrays and merge them into sorted array."""
11      # test base case size of array equals 1
12      if (high - low) >= 1: # if not base case
13          middle1 = (low + high) // 2 # calculate middle of array
14          middle2 = middle1 + 1 # calculate next element over
15
16          # output split step
17          print(f'split: {subarray_string(data, low, high)}')
18          print(f' {subarray_string(data, low, middle1)}')
19          print(f' {subarray_string(data, middle2, high)}
')
20
21          # split array in half then sort each half (recursive calls)
22          sort_array(data, low, middle1) # first half of array
23          sort_array(data, middle2, high) # second half of array
24
25          # merge two sorted arrays after split calls return
26          merge(data, low, middle1, middle2, high)
27

Lines 29–61 define function merge. Lines 40–50 in merge loop until the end of either subarray is reached. Line 43 tests which element at the beginning of the arrays is smaller. If the element in the left array is smaller or equal, line 44 places it in position in the combined array. If the element in the right array is smaller, line 48 places it in position in the combined array. When the while loop completes, one entire subarray has been placed in the combined array, but the other subarray still contains data. Line 53 tests whether the left array has reached the end. If so, line 54 uses slices to fill the appropriate elements of the combined array with the elements of data that represent the right array. If the left array has not reached the end, then the right array must have reached the end, and line 56 uses slices to fill the appropriate elements of the combined array with the elements of data that represent the left array. Finally, line 58 copies the combined array into the original array that data references.

28  # merge two sorted subarrays into one sorted subarray
29  def merge(data, left, middle1, middle2, right):
30      left_index = left # index into left subarray
31      right_index = middle2 # index into right subarray
32      combined_index = left # index into temporary working array
33      merged = [0] * len(data) # working array
34
35      # output two subarrays before merging
36      print(f'merge: {subarray_string(data, left, middle1)}')
37      print(f' {subarray_string(data, middle2, right)}')
38
39      # merge arrays until reaching end of either
40      while left_index <= middle1 and right_index <= right:
41          # place smaller of two current elements into result
42          # and move to next space in arrays
43          if data[left_index] <= data[right_index]:
44             merged[combined_index] = data[left_index]
45             combined_index += 1
46             left_index += 1
47          else:
48             merged[combined_index] = data[right_index]
49             combined_index += 1
50             right_index += 1
51
52      # if left array is empty
53      if left_index == middle2: # if True, copy in rest of right array
54          merged[combined_index:right + 1] = data[right_index:right + 1]
55      else: # right array is empty, copy in rest of left array
56          merged[combined_index:right + 1] = data[left_index:middle1 + 1]
57
58      data[left:right + 1] = merged[left:right + 1] # copy back to data
59
60      # output merged array
61      print(f' {subarray_string(data, left, right)}
')
62

Throughout the algorithm, we display portions of the array to show the split and merge operations. Each time we call function subarray_string to create and display a string containing the appropriate subarray’s items. Line 65 creates a string of spaces that ensures the first subarray element aligns properly. Line 66 joins the appropriate elements of data separated by a space and appends that string to the one created in line 65. Line 67 returns the result.

63  # method to output certain values in array
64  def subarray_string(data, low, high):
65      temp = ' ' * low # spaces for alignment
66      temp += ' '.join(str(item) for item in data[low:high + 1])
67      return temp
68

The main function creates the array to sort and calls merge_sort to sort the data:

69  def main():
70      data = np.array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58])
71      print(f'Unsorted array: {data}
')
72      merge_sort(data)
73      print(f'
Sorted array: {data}
')
74
75  # call main if this file is executed as a script
76  if __name__ == '__main__':
77      main()