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:

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 left and right in each recursive call until two adjacent elements are obtained.

• Now begins the sorting process. The i and 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 j, 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!

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.