Python Data Structures and Algorithms

Merge sort

The merge sort algorithm is based on the divide and conquer rule. Given a list of unsorted elements, we split the list into approximately two halves. We continue to divide the 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 unsorted ...