# shellSort.py

import time
from arrUtils import *


def shellSort(elems):
  # Start with a big h, then reduce
  n = len(elems)
  h = n//2

  # elems[0..h-1] are already in gapped order;
  # keep adding one more elem until list
  # is h sorted
  while h > 0:
    for i in range(h, n):
      val = elems[i]
      # shift earlier h-sorted elems until correct
      # location for elems[i] is found
      j = i
      while j >= h and val < elems[j-h]:
        elems[j] = elems[j-h]
        j -= h
      elems[j] = val
    h = h//2


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