Merge sort in Python
Merge sort is one of the most prominent divide-and-conquer sorting algorithms in the modern era. It can be used to sort the values in any traversable data structure such as a list.
The theory
Merge sort works by splitting the input list into two halves, repeating the process on those halves, and finally merging the two sorted halves together.
The algorithm first moves from top to bottom, dividing the list into smaller and smaller parts until only the separate elements remain.
From there, it moves back up, ensuring that the merging lists are sorted.
Implementation
Here is the code for merge sort in Python:
def mergeSort(myList):if len(myList) > 1:mid = len(myList) // 2left = myList[:mid]right = myList[mid:]# Recursive call on each halfmergeSort(left)mergeSort(right)# Two iterators for traversing the two halvesi = 0j = 0# Iterator for the main listk = 0while i < len(left) and j < len(right):if left[i] <= right[j]:myList[k] = left[i]i += 1else:myList[k] = right[j]j += 1k += 1# For all the remaining valueswhile i < len(left):myList[k] = left[i]i += 1k += 1while j < len(right):myList[k]=right[j]j += 1k += 1myList = [54,26,93,17,77,31,44,55,20]mergeSort(myList)print(myList)
This is the recursive approach for implementing merge sort. The steps needed to obtain the sorted array through this method can be found below:
-
The list is divided into
leftandrightin each recursive call until two adjacent elements are obtained. -
Now begins the sorting process. The
iandjiterators traverse the two halves in each call. Thekiterator traverses the whole lists and makes changes along the way. -
If the value at
iis smaller than the value atj,left[i]is assigned to themyList[k]slot andiis incremented. If not, thenright[j]is chosen. -
This way, the values being assigned through
kare all sorted. -
At the end of this loop, one of the halves may not have been traversed completely. Its values are simply assigned to the remaining slots in the list.
And with that, the merge sort has been implemented!
Time complexity
The algorithm works in O(nlogn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.
Test yourself
Now that you've learned about merge sort and have seen an implementation of merge sort in ascending order, challenge yourself by modifying the following code to sort the array in descending order.
def mergeSort(myList):if len(myList) > 1:mid = len(myList) // 2left = myList[:mid]right = myList[mid:]# Recursive call on each halfmergeSort(left)mergeSort(right)# Two iterators for traversing the two halvesi = 0j = 0# Iterator for the main listk = 0while i < len(left) and j < len(right):if left[i] <= right[j]:myList[k] = left[i]i += 1else:myList[k] = right[j]j += 1k += 1while i < len(left):myList[k] = left[i]i += 1k += 1while j < len(right):myList[k] = right[j]j += 1k += 1
