In this article, we will be having a look at an efficient sorting algorithm – Merge Sort in Python. The merge sort algorithm is used to sort existing data in an ascending or descending order. Let’s look into how we can make use of the algorithm and implement it in Python.
Working of Merge Sort in Python
Merge sort is a general-purpose sorting technique purely based on Divide and Conquer Approach.
In the Divide and Conquer technique, the elements are divided into smaller parts or lists. Then the appropriate function is applied to each half of the main input list. Further, the halves are merged together to get the result.
Merge Sortis a recursive technique wherein the unsorted elements are divided into two halves/parts and the function calls itself for the parted halves in a manner such that the halves keep recursively dividing themselves into two parts until the entire array is sorted.
It recursively calls itself for the halves or sub-lists until it gets all the elements separated and that no further division is possible i.e. every sub-list contains 1 (single) element.
Then, the elements are sorted using the basic technique of comparison and swap. Finally, it merges all the elements together to get the final sorted list of data items.
Let’s understand the working of Merge sort in Python with the help of an example;
Consider the list of elements: 11, 31, 7, 41, 101, 56, 77, 2
As mentioned above, initially, we divide the original list of data elements int two halves.
As the above original array contains 8 elements, we divide the array into a sub-array of 4 elements. The array keeps recursively dividing itself into sub-lists,until a single element is obtained per sub-list i.e. no more further division is possible.
As clearly stated, the list gets recursively divided into two parts/halves until all the elements are segregated as an individual one.
After the splitting of elements, you will see the individual elements as follows:
Once the elements are separated, we need to combine the data elements in the same manner as we had split the elements.
Consider the elements 11 and 31. As the are in their sorted positions, we combine them and merge them together in an array. Elements 7 and 41 also appear in their sorted places, so we merge them as well.
Now, if you have a look at elements 101 and 56, we need to swap their positions and merge them together. In a similar fashion, elements 77 and 2 are swapped with respect to their positions and merged together.
Taking it ahead, in the second iteration, we compare the sub-array of two elements with the other sub-array and if the elements are found sorted, we merge the sub-arrays altogether. The sub-array [11,31] is compared with [7,41] and sub-array [56,101] is compared with [2,77]. As the data items are not in their sorted order, their positions are swapped.
In the third iteration, the sub-array of 4 elements is compared with the other sub-array i.e. [7, 11, 31, 41] is compared with [2, 56, 77, 101]. As clearly visible, the elements are not in their sorted positions, so the elements are swapped and merged to get the final sorted array.
Merge Sort Algorithm
The following steps are followed in a recursive manner to perform Merge Sort and avail the appropriate results:
- Find the middle element required to divide the original array into two parts.
- Divide the original list into two halves in a recursive manner, until every sub-list contains a single element. i.e. call the merge_sort() function for every half recursively.
- Check the data-values, if found in unsorted order, swap the elements and merge the sub-lists to get the original sorted list.
Implementing Merge Sort in Python
def merge_sort(inp_arr):
size = len(inp_arr)
if size > 1:
middle = size // 2
left_arr = inp_arr[:middle]
right_arr = inp_arr[middle:]
merge_sort(left_arr)
merge_sort(right_arr)
p = 0
q = 0
r = 0
left_size = len(left_arr)
right_size = len(right_arr)
while p < left_size and q < right_size:
if left_arr[p] < right_arr[q]:
inp_arr[r] = left_arr[p]
p += 1
else:
inp_arr[r] = right_arr[q]
q += 1
r += 1
while p < left_size:
inp_arr[r] = left_arr[p]
p += 1
r += 1
while q < right_size:
inp_arr[r]=right_arr[q]
q += 1
r += 1
inp_arr = [11, 31, 7, 41, 101, 56, 77, 2]
print("Input Array:\n")
print(inp_arr)
merge_sort(inp_arr)
print("Sorted Array:\n")
print(inp_arr)
Output:
Input Array:
[11, 31, 7, 41, 101, 56, 77, 2]
Sorted Array:
[2, 7, 11, 31, 41, 56, 77, 101]
Time complexity of Merge Sort
The time complexity of Merge Sort is: O(nlogn)
Conclusion
Thus, in this article, we have understood the working of Merge sort in Python. Have a look at other sorting algorithms in Python.