Python Merge Sort Program

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)
Run Code Copy

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.

Code copied to clipboard successfully 👍