How to implement Merge Sort algorithm in Python
By Abhilash BandlaThis Python tutorial helps you to understand what is Merge sort algorithm and how Python implements this algorithm.
Algorithm of Merge Sort
This algorithm is a sorting algorithm which follows the divide and conquer principle like quicksort. This algorithm divides the given input array into two halves and calls itself recursively until all the elements are divided. Once all the elements are halved or divided, the algorithm starts merging the two sorted halves and this process repeats till all the halves are sorted.
Advantages of Merge Sort:-
- It can be applied to files of any size.
- Running time complexity of Merge sort is O(n log (n)) for best case, average case and worst case.
Disadvantages of Merge Sort:-
- Merge sort requires more space than other sorting algorithms.
- Merge sort is less efficient than other sorting algorithms.
Implementation of Merge Sort in Python
Let’s try to implement merge sort algorithm in Python with the below code.
Source Code: Merge sort in Python
def merge_sort(arr, begin, end):
if end - begin > 1:
middle = (begin + end)//2
merge_sort(arr, begin, middle)
merge_sort(arr, middle, end)
merge_list(arr, begin, middle, end)
def merge_list(arr, begin, middle, end):
left = arr[begin:middle]
right = arr[middle:end]
k = begin
i = 0
j = 0
while (begin + i < middle and middle + j < end):
if (left[i] <= right[j]):
arr[k] = left[i]
i = i + 1
else:
arr[k] = right[j]
j = j + 1
k = k + 1
if begin + i < middle:
while k < end:
arr[k] = left[i]
i = i + 1
k = k + 1
else:
while k < end:
arr[k] = right[j]
j = j + 1
k = k + 1
arr = input('Enter the list of numbers: ').split()
arr = [int(x) for x in arr]
merge_sort(arr, 0, len(arr))
print('Sorted list: ', end='')
print(arr)Output:-
Case-1 :
Enter the list of numbers: 9 8 7 6 5 4 3 2 1 0 Sorted list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Case-2:
Enter the list of numbers: 5 6 1 3 8 9 2 7 4 0 Sorted list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
You can also read,
One major disadvantage of merge sort in python is that ‘Merge sort requires more space than other sorting algorithms’. Is there any way that a user can intervene to this?