Merge Sort
Merge Sort algorithm is a general-purpose comparison-based sorting algorithm. Most implementations produce a stable sort, in which the order of equal elements is preserved.
Here, our method is bottom-up merge sort algorithm, which treats the list as an array of n sublists of size 1, and iteratively doubles the size, sorts and merges the sublists.
Just for practicing, I've implemented the iterative version of merge sort algorithm, copied below, and I'd appreciate it if you'd like to review any part of it for any small or big changes/improvements.
Code
import random from typing import TypeVar, List from scipy import stats T = TypeVar('T') def iterative_merge_sort(input_list: List[T]) -> List[T]: """ Iterative Bottom Up Merge Sort ----------------------------------------------- Merge Sort is a Divide and Conquer algorithm. It divides the input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge function is used for merging two halves. In this algorithm, we'd start from the smallest window size of 1 and double up the window size in each level until we'd reach to the last level, which would be the size of input list. Attributes: - Time Complexity: O(N*Log N) - In each level, there are O(N) comparisons - There are O(Log N) levels - Space Complexity: O(N) it is not an in-place sort - Stable Sort """ # Assigns the length of input list. size_of_input = len(input_list) # Creates a new list for sorted output list. temp_output_list = size_of_input * [None] # Starts from the window size 1 and doubles up window_size = 1 while window_size <= size_of_input - 1: sort_in_level(input_list, temp_output_list, window_size, size_of_input) window_size = 2 * window_size return temp_output_list def sort_in_level(input_list: List[T], temp_output_list: List[T], window_size: int, size_of_input: int) -> List[T]: """ In this method we would assign four indices for start and end indices of two sublists: - Starting Index for the first sublist - Ending Index for the first sublist - Starting Index for the second sublist - Ending Index for the second sublist Then, we'd do the divide and merge """ # Assigns the Starting Index of the first sublist to 0. first_start_index = 0 while first_start_index + window_size <= size_of_input - 1: first_end_index = first_start_index + window_size - 1 second_start_index = first_start_index + window_size second_end_index = second_start_index + window_size - 1 # In case, the Second Ending Index went over the limit, which is the length of input list. if second_end_index >= size_of_input: second_end_index = size_of_input - 1 # Merges the two sublists merge_sublists(input_list, temp_output_list, first_start_index, first_end_index, second_start_index, second_end_index) # Increments the Starting Index for the first sublist for the next sublist merging first_start_index = second_end_index + 1 # In case, any other element would be left, it'd be placed in the temp output list for i in range(first_start_index, size_of_input): temp_output_list[i] = input_list[i] # Copies to the sorted part of the output list. copy_sorted_list(input_list, temp_output_list, size_of_input) def merge_sublists(input_list: List[T], temp_output_list: List[T], first_start_index: int, first_end_index: int, second_start_index: int, second_end_index: int) -> List[T]: """ This method would merges the sublists using three simple while loops: - In the first while, we'd continue until the min length in between the two sublists. - In the second while, we'd continue if any element would be left from the sublist 1. - In the third while, we'd continue if any element would be left from the sublist 2. e.g., sublist 1 [1, 3, 5, 7, 9] e.g., sublist 2 [2, 4, 6, 8, 10, 12, 14] - First while loop generates: [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10] - Second while loop just passes, since no elements left from the first sublist. - Third while loop generates: [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10, 12, 14] """ # Assigns the Sublist 1 and temp output list indices (i, k) i = k = first_start_index # Assigns the Sublist 2 index (j) j = second_start_index # For if the size of smallest sublists: while i <= first_end_index and j <= second_end_index: # If the Sublist 1 element is smaller if input_list[i] <= input_list[j]: # Places the Sublist 1 element in the temp output list temp_output_list[k] = input_list[i] # Increments the Sublist 1 i += 1 else: # Places the Sublist 2 element in the temp output list temp_output_list[k] = input_list[j] # Increments the Sublist 2 j += 1 # Increments the temp output list k += 1 # For if any element would be left in Sublist 1 while i <= first_end_index: # Copies the Sublist 1 element in the temp output list temp_output_list[k] = input_list[i] # Increments the Sublist 1 i += 1 # Increments the temp output list k += 1 # For if any element would be left in Sublist 2 while j <= second_end_index: # Copies the Sublist 2 element in the temp output list temp_output_list[k] = input_list[j] # Increments the Sublist 2 j += 1 # Increments the temp output list k += 1 def copy_sorted_list(input_list, temp_output_list, size_of_input): """ This method copies the sorted temp output into the input list """ for i in range(size_of_input): input_list[i] = temp_output_list[i] if __name__ == "__main__": # Creates a dash line string and a new line for in between the tests. delimiter = "-" * 70 + "\n" # Generates a random integer list. TEST_LIST_INTEGER = random.sample(range(-100, 100), 15) * 3 print(f"""The unsorted integer array is: {TEST_LIST_INTEGER}""") print(delimiter) # Generates a random float list. TEST_LIST_FLOAT = stats.uniform(0, 100).rvs(45) print(f"""The unsorted float array is: {TEST_LIST_FLOAT}""") print(delimiter) # Sample float/integer test list for input. INTEGER_FLOAT_INPUT = list(TEST_LIST_INTEGER + TEST_LIST_FLOAT) # Sample float/integer test list for output. INTEGER_FLOAT_OUTPUT = sorted(INTEGER_FLOAT_INPUT) sorting_algorithms = [ ("Iterative Merge Sort", iterative_merge_sort) ] # Testing for description, func in sorting_algorithms: if (func(INTEGER_FLOAT_INPUT.copy()) == INTEGER_FLOAT_OUTPUT): print(f"{description} Test was Successful.") else: print(f"{description} Test was not Successful.") print(f"""{description} (Integer): {func(TEST_LIST_INTEGER.copy())}""") print(f"""{description} (Float): {func(TEST_LIST_FLOAT.copy())}""") print(delimiter) 
