An implementation of the merge sort algorithm in Python.

merge_sort.py

'''
The merge sort algorithm has a time complexity of O(nlogn).
It is an implementation of a Divide and Conquer rule.
'''

def mergeSort(array):
  n = len(array)
  if n == 1:
    return array

  mid = n // 2
  left = array[0:mid]
  right = array[mid:]

  return merge(mergeSort(left), mergeSort(right), n)

def merge(left, right, n):
  merged = []
  iLeft = 0
  iRight = 0
  leftLength = len(left)
  rightLength = len(right)

  for i in range(n):
    if iLeft >= leftLength:
      merged.append(right[iRight])
      iRight += 1
    elif iRight >= rightLength:
      merged.append(left[iLeft])
      iLeft += 1
    elif left[iLeft] <= right[iRight]:
      merged.append(left[iLeft])
      iLeft += 1
    else:
      merged.append(right[iRight])
      iRight += 1
    print(iLeft, iRight, merged)

  return merged