Merge sort

explanation

It is a divide and conquer way where you split the given list into 2 halves and keep on splitting until you get sub-lists containing just 1 element each. Like the left can contain [2] and right can contain [1]. Then once this end recursion condtion is met (len(lst)<=1), we merge sort these 2 lists with pointers.

The merge sort works via pointers where while left and right pointer are less than left and right list, we append to a temporary answer list.

The imporatant bit is that there can be a residue of elements remaining in either left or right list. For example, if left=[1,3] and right[2,4,5], [4,5] will be extended cuz after processing value 3 in left list, the while condition is no longer satisfied. So we need to extend the remaining ele.

And v impt to return merge(left_lst,right_lst) cuz I forgot to return the answer returned by merge_sort to the current call stack.

sol

def merge_sort(data):
    if len(data)<=1:
        return data
    mid = len(data)//2
    left = data[:mid]
    right = data[mid:]

    left_lst=merge_sort(left)
    right_lst=merge_sort(right)
    return merge(left_lst,right_lst)

def merge(left_lst, right_lst):
    left,right=0,0
    ans = []
    while left<len(left_lst) and right<len(right_lst):
        left_val,right_val=left_lst[left],right_lst[right]
        if left_val<right_val:
            ans.append(left_val)
            left+=1
        else:
            ans.append(right_val)
            right+=1
    ans.extend(left_lst[left:])
    ans.extend(right_lst[right:])
    return ans

my_list = [5, 1, 4, 2, 8]
print(f"Original: {my_list}")
sorted_list = merge_sort(my_list.copy())
print(f"Sorted: {sorted_list}")