# insertionSort.py

import time
from arrUtils import *


def insertionSort(elems):
  n = len(elems)
  if n > 1:
    for i in range(1, n):
      val = elems[i]
      j = i-1
      while j >= 0 and val < elems[j]: # Move elems > val
        elems[j+1] = elems[j]  # Shift to right
        j -= 1
      elems[j+1] = val


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