How to implement Merge Sort algorithm in Python

This 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:-




  1. It can be applied to files of any size.
  2. Running time complexity of Merge sort is O(n log (n)) for best case, average case and worst case.

Disadvantages of Merge Sort:-

  1. Merge sort requires more space than other sorting algorithms.
  2. 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,

 


Leave a Reply

Your email address will not be published. Required fields are marked *