-- ------------------------------------------------------------------- -- loadFile -- Purpose: -- Read non-empty integer lines from an input file. -- Parameters: -- fileSpec - path of the input file to read. -- Returns: -- A table containing the parsed integers in input order. -- Side effects: -- Opens and closes the input file and prints read progress. -- ------------------------------------------------------------------- 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 each integer in a table to a separate output-file line. -- Parameters: -- values - integers to write. -- fileSpec - path of the output file to create or replace. -- Returns: -- No value. -- Side effects: -- Creates and closes the output file and prints 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 -- ------------------------------------------------------------------- -- merge -- Purpose: -- Merge two sorted tables into one sorted table. -- Parameters: -- left - sorted first input table. -- right - sorted second input table. -- Returns: -- A new table containing every value in ascending order. -- Side effects: -- Removes values from the input tables as it merges them. -- ------------------------------------------------------------------- local function merge(left, right) local result = {} while #left > 0 and #right > 0 do if left[1] <= right[1] then table.insert(result, table.remove(left, 1)) else table.insert(result, table.remove(right, 1)) end end while #left > 0 do table.insert(result, table.remove(left,1)) end while #right > 0 do table.insert(result, table.remove(right,1)) end return result; end -- ------------------------------------------------------------------- -- mergeSort -- Purpose: -- Recursively divide a table, sort each half, and merge them. -- Parameters: -- values - integers to sort. -- Returns: -- A table containing the values in ascending order. -- Side effects: -- Creates sorted subtables without modifying the input table. -- ------------------------------------------------------------------- local function mergeSort(values) if #values <= 1 then return values end local left = {} local right = {} local middle = math.floor(#values/2) local i = 0; for i, value in ipairs(values) do if i <= middle then table.insert(left, value); else table.insert(right, value); end end left = mergeSort(left) right = mergeSort(right) return merge(left, right) end -- ------------------------------------------------------------------- -- doSort -- Purpose: -- Time the merge sort and save its sorted result. -- Parameters: -- values - table of integers to sort. -- Returns: -- Elapsed CPU time in seconds. -- Side effects: -- Prints progress and writes the sorted values to the output file. -- ------------------------------------------------------------------- local function doSort(values) io.write("SORTING ELEMENTS...") local startTime = os.clock() local values = mergeSort(values) local endTime = os.clock() print("DONE.") saveFile(values, "D:/Sorting/Output_LUA.txt") return endTime - startTime end print("=========MERGESORT LUA==========") local values = loadFile("D:/Sorting/Sorting_Input.txt") local elapsed = doSort(values) print("==========RUN COMPLETE==========") print(string.format("MERGESORT TOOK %.6f SECONDS.", elapsed)) print("================================")