Merge Sort

#!/usr/bin/evn python

# Functiont to sort data in merge sort algorithm
def mergeSort(data):
    
    if len(data) > 1:
        # Devided the array in two part
        mid = len(data)//2
        leftHalf = data[:mid]
        rightHalf = data[mid:]
        
        # Recursively call the same function
        mergeSort(leftHalf)
        mergeSort(rightHalf)

        i=0
        j=0
        k=0
        
        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] < rightHalf[j]:
                data[k] = leftHalf[i]
                i=i+1
            else:
                data[k] = rightHalf[j]
                j=j+1
            k=k+1

        while i < len(leftHalf):
            data[k] = leftHalf[i]
            i=i+1
            k=k+1

        while j < len(rightHalf):
            data[k] = rightHalf[j]
            j=j+1
            k=k+1

numList = [5,8,1,6,3,7,2,4,9]
print('Before sort:')
print(numList)
# Calling 'mergeSort' function by passing number array
mergeSort(numList)
print('After sort:')
print(numList)


# ***** Output *****
Before sort:
[5, 8, 1, 6, 3, 7, 2, 4, 9]
After sort:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Recommended for you