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.
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.
Here is the code for merge sort in Python:
def mergeSort(myList): if len(myList) > 1: mid = len(myList) // 2 left = myList[:mid] right = myList[mid:] # Recursive call on each half mergeSort(left) mergeSort(right) # Two iterators for traversing the two halves i = 0 j = 0 # Iterator for the main list k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # The value from the left half has been used myList[k] = left[i] # Move the iterator forward i += 1 else: myList[k] = right[j] j += 1 # Move to the next slot k += 1 # For all the remaining values while i < len(left): myList[k] = left[i] i += 1 k += 1 while j < len(right): myList[k]=right[j] j += 1 k += 1 myList = [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
right in each recursive call until two adjacent elements are obtained.
Now begins the sorting process. The
j iterators traverse the two halves in each call. The
k iterator traverses the whole lists and makes changes along the way.
If the value at
i is smaller than the value at
left[i] is assigned to the
myList[k] slot and
i is incremented. If not, then
right[j] is chosen.
This way, the values being assigned through
k are 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!
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.
View all Courses