Merge Sort Program - Python

Python Merge Sort

In this tutorial, we have implemented Merge Sort Algorithm. Also, by default, the merge_sort() function in the following program sorts the list in ascending order.

To get the descending order, all you have to do is just reverse the list.

Python Program

def merge_sort(nlist, start, end):
    #sorts the list from indexes start to end - 1 inclusive
    if end - start > 1:
        mid = (start + end)//2
        merge_sort(nlist, start, mid)
        merge_sort(nlist, mid, end)
        merge_list(nlist, start, mid, end)
 
def merge_list(nlist, start, mid, end):
    left = nlist[start:mid]
    right = nlist[mid:end]
    k = start
    i = 0
    j = 0
    while (start + i < mid and mid + j < end):
        if (left[i] <= right[j]):
            nlist[k] = left[i]
            i = i + 1
        else:
            nlist[k] = right[j]
            j = j + 1
        k = k + 1
    if start + i < mid:
        while k < end:
            nlist[k] = left[i]
            i = i + 1
            k = k + 1
    else:
        while k < end:
            nlist[k] = right[j]
            j = j + 1
            k = k + 1

#input list
aList = [1, 74, 96, 5, 42, 63]

merge_sort(aList, 0, len(aList))
print('Sorted List after Merge Sort, in Ascending Order\n', aList)

aList.reverse()
print('Sorted List after Merge Sort, in Descending Order\n', aList)

Output

Sorted List after Merge Sort, in Ascending Order
 [1, 5, 42, 63, 74, 96]
Sorted List after Merge Sort, in Descending Order
 [96, 74, 63, 42, 5, 1]

Conclusion

In this tutorial of Python Examples, we learned how to implement Merge Sort Algorithm in Python.