Hands-On Data Structures and Algorithms with Python - Second Edition

Merge sort

Merge sort algorithms are based on the divide and conquer rule. Given a list of unsorted elements, we split the list into two approximate halves. We continue to divide the list into two halves recursively.

After a while, the sublists created as a result of the recursive call will contain only one element. At that point, we begin to merge the solutions in the conquer or merge step:

    def merge_sort(unsorted_list):         if len(unsorted_list) == 1:             return unsorted_list         mid_point = int((len(unsorted_list))//2)         first_half = unsorted_list[:mid_point]         second_half = unsorted_list[mid_point:]         half_a = merge_sort(first_half)         half_b = merge_sort(second_half)         return merge(half_a, half_b) 

Our implementation starts by accepting the list of ...