python merge sort

Merge sort is a sorting algorithm that uses the divide and conquer technique. It works by dividing the unsorted list into n sublists, each containing one element, and then repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining. Here's a Python implementation of merge sort:

def merge_sort(arr):
    # base case
    if len(arr) <= 1:
        return arr
    
    # divide the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # recursively sort the two halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    # merge the sorted halves
    sorted_arr = []
    i = j = 0
    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            sorted_arr.append(left_half[i])
            i += 1
        else:
            sorted_arr.append(right_half[j])
            j += 1
    sorted_arr += left_half[i:]
    sorted_arr += right_half[j:]
    
    return sorted_arr

To use the merge_sort function, simply pass in an unsorted list:

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_list = merge_sort(my_list)
print(sorted_list)

This will output the sorted list:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]