local function siftDown(values, root, last)
  while root * 2 <= last do
    local child = root * 2
    if child + 1 <= last 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 loadFile(fileSpec)
  print("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)
  print("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 performSort(values)
  print("SORTING ELEMENTS...")
  local startTime = os.clock()
  for start = math.floor(#values / 2), 1, -1 do siftDown(values, start, #values) end
  for last = #values, 2, -1 do
    values[1], values[last] = values[last], values[1]
    siftDown(values, 1, last - 1)
  end
  local endTime = os.clock()
  print("DONE.")
  return endTime - startTime;
end

print("***HEAPSORT 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("HEAPSORT TOOK %.6f SECONDS.", elapsed))