merge_sort.py

# Merge Sort Algorithm - sorts a sequence in place recursively, for additional
# convenience returns the sequence.
# Time complexity: nlgn
# The script is Python2-3 compatible.
from __future__ import print_function


def merge_sort(seq):
    if len(seq) == 1:
        return seq

    middle = len(seq) // 2
    left = merge_sort(seq[:middle])
    right = merge_sort(seq[middle:])

    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            seq[k] = left[i]
            i += 1
        else:
            seq[k] = right[j]
            j += 1
        k += 1

    leftover = left if (i < j) else right
    counter = i if (leftover == left) else j

    while counter < len(leftover):
        seq[k] = leftover[counter]
        counter += 1
        k += 1
    return seq
    

if __name__ == '__main__':
    seq = [4, 2, 9, 5, 3, 0, 7]
    print(merge_sort(seq))