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

-- -------------------------------------------------------------------
-- loadFile
-- Purpose:
--   Read non-blank integer records from the named input file into the program collection or shared array.
-- Parameters:
-- fileSpec - input or output file path.
-- Returns:
--   The loaded integer sequence or the count/status provided by this implementation.
-- Side effects:
--   Opens and closes the input file, populates the collection or shared array, and may update its element count.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- saveFile
-- Purpose:
--   Write the sorted integer collection or shared array to the named output file, one value per line.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- fileSpec - input or output file path.
-- Returns:
--   No value; writes the output file.
-- Side effects:
--   Creates or replaces the output file and reports file progress.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- siftDown
-- Purpose:
--   Restore max-heap order below the specified root within the active heap range.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- root - current heap root index.
-- start - inclusive first index of the active range.
-- finish - exclusive end index of the active range.
-- Returns:
--   No value; rearranges the range in place.
-- Side effects:
--   Mutates the sequence and may stop once the heap property is restored.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- heapSort
-- Purpose:
--   Sort the selected range in place with heapsort, the worst-case introsort fallback.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- start - inclusive first index of the active range.
-- finish - exclusive end index of the active range.
-- Returns:
--   No value; sorts the selected range in place.
-- Side effects:
--   Mutates the range and increments the heapsort counter where present.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- insertionSort
-- Purpose:
--   Sort the selected range in place with insertion sort, which is efficient for short ranges.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- start - inclusive first index of the active range.
-- finish - exclusive end index of the active range.
-- Returns:
--   No value; sorts the selected range in place.
-- Side effects:
--   Mutates the range and increments the insertion-sort counter where present.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- partition
-- Purpose:
--   Partition the selected range around its middle-element pivot and return the first index of the right-hand range.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- start - inclusive first index of the active range.
-- finish - exclusive end index of the active range.
-- Returns:
--   The first index of the right partition, which is also the left boundary of the recursive ranges.
-- Side effects:
--   Reorders the range in place while inward scans keep each access inside the active bounds.
-- -------------------------------------------------------------------
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
   
-- -------------------------------------------------------------------
-- introSort
-- Purpose:
--   Sort the selected range in place: insertion sort for short ranges, heapsort when the depth budget expires, otherwise partition and recurse.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- start - inclusive first index of the active range.
-- finish - exclusive end index of the active range.
-- maxdepth - remaining partition-depth budget before heapsort fallback.
-- Returns:
--   No value; sorts the selected range in place.
-- Side effects:
--   Mutates the range and updates the introsort counter; recursive calls reduce the depth budget.
-- -------------------------------------------------------------------
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

-- -------------------------------------------------------------------
-- log2
-- Purpose:
--   Compute the integer base-2 size estimate used to initialize introsort depth.
-- Parameters:
-- value - positive integer used to compute the base-2 size estimate.
-- Returns:
--   An integer base-2 size estimate.
-- Side effects:
--   Does not modify the input.
-- -------------------------------------------------------------------
local function log2(value)
  local val = value
  local num = 0
  while val > 1 do
    val = val / 2
    num = num + 1
  end
  return num
end

-- -------------------------------------------------------------------
-- performSort
-- Purpose:
--   Choose the initial depth budget, time the top-level introsort, and report completion.
-- Parameters:
-- values - integer sequence to read, sort, or write; range operations modify it in place.
-- Returns:
--   Elapsed time measured by this implementation.
-- Side effects:
--   Starts and stops a timer, prints progress, and invokes introsort on the full sequence.
-- -------------------------------------------------------------------
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("--------------------------------")