Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # divide array into 2 parts
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # sort recursively from left part and right part
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # merge two sorted arrays
    return merge(left_half, right_half)


def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0

    # merge two arrays
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    # add remaining elements to the result
    # either of these two arrays should be left to handle, the remaining are sorted can be appended safely
    result.extend(left[left_idx:])
    result.extend(right[right_idx:])

    return result


# Example
arr = [12, 11, 13, 5, 6, 7]
print("Original Array:", arr)
sorted_arr = merge_sort(arr)
print("Sorted Array:", sorted_arr)
# Original Array: [12, 11, 13, 5, 6, 7]
# Sorted Array: [5, 6, 7, 11, 12, 13]