from pathlib import Path import time from typing import List, Union import math # ------------------------------------------------------------------- # load_file # Purpose: # Read integer lines from a file and return them in a list. # Parameters: # fileSpec - path of the input file to read. # Returns: # The parsed integers in input order. # Side effects: # Opens and closes the input file and prints read progress. # ------------------------------------------------------------------- def load_file(fileSpec: Union[str, Path]) -> List[int]: print("READING INPUT FILE...",end="") values: List[int] = [] with Path(fileSpec).open(encoding="ascii") as input_file: for line_number, line in enumerate(input_file, start=1): text = line.strip() if text: try: values.append(int(text)) except ValueError as error: raise ValueError( f"Invalid integer on line {line_number}: {text!r}" ) from error print("DONE.") return values # ------------------------------------------------------------------- # save_file # Purpose: # Write each integer in a list to its own output-file line. # Parameters: # values - integers to write. # fileSpec - output file path. # Returns: # None. # Side effects: # Creates and closes the output file and prints progress. # ------------------------------------------------------------------- def save_file(values: List[int], fileSpec: Union[str, Path]) -> None: print("SAVING OUTPUT FILE...",end="") with Path(fileSpec).open("w", encoding="ascii") as output_file: for value in values: print(value, file=output_file) print("DONE.") # ------------------------------------------------------------------- # merge # Purpose: # Merge two sorted lists into a new sorted list. # Parameters: # left - sorted first input list. # right - sorted second input list. # Returns: # A new list containing all values in ascending order. # Side effects: # Removes values from the input lists as it merges them. # ------------------------------------------------------------------- def merge(left: List[int], right: List[int]) -> List[int]: result: List[int] = [] while len(left) > 0 and len(right) > 0: if left[0] <= right[0]: result.append(left[0]) left.pop(0) else: result.append(right[0]) right.pop(0) for l in range(len(left)): result.append(left[l]) for r in range(len(right)): result.append(right[r]) return result # ------------------------------------------------------------------- # merge_sort # Purpose: # Recursively divide a list, sort each half, and merge them. # Parameters: # values - integers to sort. # Returns: # A list containing the values in ascending order. # Side effects: # Creates sorted sublists without modifying the input list. # ------------------------------------------------------------------- def merge_sort(values: List[int]) -> List[int]: if len(values) <=1: return values; left: List[int] = [] right: List[int] = [] middle = math.floor(len(values)/2) for i in range(len(values)): if i < middle: left.append(values[i]) else: right.append(values[i]) left = merge_sort(left) right = merge_sort(right) return merge(left,right) # ------------------------------------------------------------------- # do_sort # Purpose: # Time the merge sort, save its sorted result, and return elapsed time. # Parameters: # values - integers to sort. # Returns: # Elapsed sorting time in seconds. # Side effects: # Prints progress and writes the sorted values to the output file. # ------------------------------------------------------------------- def do_sort(values: List[int]) -> float: vals: List[int] = [] print("SORTING ELEMENTS...",end="") startTime = time.perf_counter() vals = merge_sort(values) endTime = time.perf_counter() print("DONE.") save_file(vals, "D:/Sorting/Output_Python.txt") return endTime - startTime # ------------------------------------------------------------------- # main # Purpose: # Run the input, sort, output, and timing-report workflow. # Parameters: # None. # Returns: # None. # Side effects: # Reads and writes files and prints timing and completion messages. # ------------------------------------------------------------------- def main() -> None: print("========MERGESORT PYTHON=========") values = load_file("D:/Sorting/Sorting_Input.txt") elapsed = do_sort(values) print("==========RUN COMPLETE===========") print(f"MERGESORT TOOK {elapsed:.6f} SECONDS.") print("=================================") if __name__ == "__main__": main()