mergesort.py

# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:

        # Devide!

        # Finding the mid of the array
        mid = len(arr)//2
        # Dividing the array elements
        left = arr[:mid]
        # into 2 halves
        right = arr[mid:]

        # Conquer!

        # recursive calls to mergeSort for left and right sub arrays
        # Sorting the first half
        mergeSort(left)
        # Sorting the second half
        mergeSort(right)

        # initalizes pointers for left (i) right (j) and output array (k)
        # 3 initalization operations
        i = j = k = 0

        # Combine!

        # Copy data to temp arrays L[] and R[]
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

# Code to print the list


def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()


# Driver Code
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    print("Given array is", end="\n")
    printList(arr)
    mergeSort(arr)
    print("Sorted array is: ", end="\n")
    printList(arr)