Which by magic (or the logic behind the algorithm) is sorted.
Well, we talked about it is one of the efficient sorting algorithm. That means it runs in O(N log(N)) time.
That means, if you have a list of N unsorted elements, it will take N log(N) operations.
Is that true for Merge Sort?
How many layers do you have in the algorithm?
Well, for each layer you half the size of each sublist. You can do that log(N) times.
For each layer, you do N comparisons. That results in N log(N) operations, hence, the O(N log(N)) time complexity.
def merge_sort(my_list): if len(my_list) <= 1: return my_list mid = len(my_list)//2 left_list = my_list[:mid] right_list = my_list[mid:] merge_sort(left_list) merge_sort(right_list) index_left = 0 index_right = 0 index_main = 0 while index_left < len(left_list) and index_right < len(right_list): if right_list[index_right] < left_list[index_left]: my_list[index_main] = right_list[index_right] index_right += 1 index_main += 1 else: my_list[index_main] = left_list[index_left] index_left += 1 index_main += 1 while index_left < len(left_list): my_list[index_main] = left_list[index_left] index_left += 1 index_main += 1 while index_right < len(right_list): my_list[index_main] = right_list[index_right] index_right += 1 index_main += 1 def main(): my_list = [19, 56, 8, -6, -3, 27, -9, -29] print(my_list) merge_sort(my_list) print(my_list) if __name__ == "__main__": main()
That is awesome.
Want to learn more about sorting. Check out the Insertion Sort, which is also one of the sorting algorithms you need to master. It is not as efficient, but it has one advantage you need to understand.