# mergeSort.py

import time
from arrUtils import *


def mergeSort(elems):
  msort(elems, 0, len(elems)-1) 

def msort(elems, left, right):
  if left < right:
    mid = left+(right-left)//2
    # Sort halves
    msort(elems, left, mid)
    msort(elems, mid+1, right)
    merge(elems, left, mid, right)


def merge(elems, left, mid, right):
  # Merge elems[left..mid] and elems[mid+1..right]
  leftSize = mid - left+1
  rightSize = right - mid

  # create temp lists
  leftTemp = [0] * (leftSize)
  rightTemp = [0] * (rightSize)
  for i in range(0, leftSize):
    leftTemp[i] = elems[left+i]
  for j in range(0, rightSize):
    rightTemp[j] = elems[mid+1+j]

  # Merge temps into elems[left..right]
  i = 0     # index of first sublist
  j = 0     # index of second sublist
  k = left  # index of merged sublist
  while i < leftSize and j < rightSize:
    if leftTemp[i] <= rightTemp[j]:
      elems[k] = leftTemp[i]
      i += 1
    else:
      elems[k] = rightTemp[j]
      j += 1
    k += 1

  # Copy remaining elements of leftTemp
  while i < leftSize:
    elems[k] = leftTemp[i]
    i += 1
    k += 1

  # Copy remaining elements of rightTemp
  while j < rightSize:
    elems[k] = rightTemp[j]
    j += 1
    k += 1


if __name__ == "__main__":
  n = int(input("n? "))
  elems = genArr(n)
  start = time.time()
  mergeSort(elems)
  printPartArr(elems)
  print(f"Time: {(time.time()-start):.4f} secs")