local Heaps = 0
local Intros = 0
local Inserts = 0

local function loadFile(fileSpec)
  io.write("READING INPUT FILE...")
  local inputFile = assert(io.open(fileSpec, "r"))
  local values = {}
  for line in inputFile:lines() do
    if line:match("%S") then table.insert(values, assert(tonumber(line))) end
  end
  inputFile:close()
  print("DONE.")
  return values;
end

local function saveFile(values, fileSpec)
  io.write("SAVING OUTPUT FILE...")
  local outputFile = assert(io.open(fileSpec, "w"))
  for _, value in ipairs(values) do outputFile:write(value, "\n") end
  outputFile:close()
  print("DONE.")
end

local function siftDown(values,root,start,finish)
  while start + 2 * (root - start) + 1 < finish do
    local child = start + 2 * (root - start) + 1
    if child + 1 < finish and values[child] < values[child + 1] then child = child + 1 end
    if values[root] >= values[child] then return end
    values[root], values[child] = values[child], values[root]
    root = child
  end
end

local function heapSort(values, start, finish)
  Heaps = Heaps + 1
  for root = start + math.floor((finish - start) / 2) - 1, start, -1 do  siftDown(values, root, start, finish) end
  for last = finish - 1, start + 1, -1 do
    local temp = values[start]
    values[start] = values[last]
    values[last] = temp
    siftDown(values, start, start, last)
  end      
end

local function insertionSort(values, start, finish)
  Inserts = Inserts + 1
  for index = start, finish - 1, 1 do
    local value = values[index]
    local pos = index - 1
    while pos >= start and values[pos] > value do
      values[pos + 1] = values[pos]
      pos = pos - 1
    end
    values[pos + 1] = value
  end  
end

local function partition(values, start, finish)
  local temp = 0
  local left = start
  local right = finish - 1
  local pivot = values[start + math.floor((finish - start) / 2)]
  while left <= right do
    while values[left] < pivot do left = left + 1 end
    while values[right] > pivot do right = right - 1 end
    if left <= right then
      temp = values[left]
      values[left] = values[right]
      values[right] = temp
      left = left + 1
      right = right - 1
    end
  end
  return left
end
   
local function introSort(values, start, finish, maxdepth)
  Intros = Intros + 1
  local part = 0
  local length = finish - start
  if length <= 1 then return 
  elseif length < 16 then insertionSort(values, start, finish) 
  elseif maxdepth <= 0 then heapSort(values, start, finish) 
  else 
    part = partition(values, start, finish)
    introSort(values, start, part, maxdepth - 1)
    introSort(values, part, finish, maxdepth - 1)
  end
end

local function log2(value)
  local val = value
  local num = 0
  while val > 1 do
    val = val / 2
    num = num + 1
  end
  return num
end

local function performSort(values)
  io.write("SORTING ELEMENTS...")
  local startTime = os.clock()
  local maxdepth = 0
  if #values > 1 then
    maxdepth = log2(#values) * 2
  end
  introSort(values, 1, #values + 1, maxdepth)
  local endTime = os.clock()
  print("DONE.")
  return endTime - startTime
end

print("=========INTROSORT LUA==========")
local values = loadFile("D:/Sorting/Sorting_Input.txt")
local elapsed = performSort(values)
saveFile(values, "D:/Sorting/Output_LUA.txt")
print("==========RUN COMPLETE==========")
print(string.format("INTROSORT TOOK %.6f SECONDS.", elapsed))
print("================================")
print("SORT CALLED | TIMES")
print("------------+-------------------")
print(string.format("Intro       | %d", Intros))
print(string.format("Insert      | %d", Inserts))
print(string.format("Heap        | %d", Heaps))
print("--------------------------------")