Previously, we’ve covered binary search and selection sort. This time, we’ll be covering another sorting algorithm – merge sort. Merge sort is a little different from selection sort. While selection sort can’ only be used to sort an unsorted list, merge sort can be utilized to merge two different sorted lists, in addition to sorting an unsorted list.
The core idea of merge sort is an instance of a divide and conquer approach. First, the entire list/array is split apart into left and right halves. Afterwards, the left half of the array is also divided in half. This recurs until there is only one element in the left and right halves, until the array halves cannot be split further. Afterwards, the values are merged together, being compared and place in sorted order.
This process recurs, gradually sorting and merging groups, until there is only one group with all the elements in their proper order. It is critical to remember that every-time a group is created the sorted order must be maintained.
Here’s an example of the technique, broken into dividing and merging phases.
Dividing Phase:
Assuming we have an array with the following values: [3, 8, 9, 2, 6, 7], the process will look something like this.
Division 1: [3, 8, 9][2, 6, 7]
Division 2: [3] [8, 9] [2] [6,7]
Division 3: [3] [8] [9] [2] [6] [7]
Now comes the merging phase.
Merging Phase:
Merge 1: [3, 8] [2,9] [6,7]
Merge 2: [2, 3, 8, 9][6, 7]
Merge 3: [2, 3, 6, 7, 8, 9]
If two lists are being merged, it is important to compare the elements before they are merged into a single list. Otherwise, the merged list will contain all the sorted elements of one list and then all the sorted elements of the other list.
So let’s make sure we understand the steps to implementing merge sort:
- We start with an unsorted list and split it in half.
2. We split the left half of the array into halves.
3. We keep splitting until there is just one element per half.
4. We compare each of the elements
5. The elements are merged into one group, in order.
6. The process continues until the entire array has been sorted and merged.
Now we can try writing merge sort in Python.
This implementation will be a recursive implementation. When writing a recursive algorithm, remember that the algorithm must have a base-case, or a case where the recursion ends.
In order to implement merge sort in Python, the algorithm can be structured as follows:
def merge_sort(array):
# Only if there are two or more elements
if len(array) > 1:
# get the midpoint in the array
mid = len(array) // 2
# left half is everything before the mid
left = array[:mid]
# right half is everything after the midpoint
right = array[mid:]
# recur the splits on the left and right halves
merge_sort(left)
merge_sort(right)
# we need variables to track the iteration through the arrays
x = 0
y = 0
# Iterator for the main list
z = 0
# here we copy the data into temporary arrays that store the left and right halves
# as long as there are still values within the left and right half of the arrays
# compare the values and swap positions
while x < len(left) and y < len(right):
# if left value is smaller than the right value
if left[x] <= right[y]:
# place the left position into the sorted array
array[z] = left[x]
# update left position
x = x + 1
else:
array[z] = right[y]
y = y + 1
# move to the next portion of the array
z = z + 1
# If there are any elements left over in the left half of the array
# We fill in the primary array with the remaining left values and then move the iterators up
while x < len(left):
array[z] = left[x]
x += 1
z += 1
# Do the same thing for the right half of the array
while y < len(right):
array[z] = right[y]
y += 1
z += 1
listy = [35, 72, 29, 55, 41, 27, 79, 11, 23, 56, 50]
merge_sort(listy)
print(listy)
Here’s the sorted list:
[11, 23, 27, 29, 35, 41, 50, 55, 56, 72, 79]
CriticallyCoding 