What is merge sort?

Merge Sort is a sorting algorithm based on the "divide and conquer" principle. It recursively divides the array into smaller subarrays until only subarrays of one element remain (which are considered sorted). Then, it gradually merges these sorted subarrays to create a larger sorted array.

The algorithm consists of two main stages:

1. Division: The array is recursively split in half until each subarray contains only one element.
2. Merging: Sorted subarrays are merged pairwise to create new, larger sorted subarrays. This process continues until all subarrays are combined into one sorted array.

The merge function takes two sorted subarrays and combines them into one sorted array. This is done by comparing the first elements of each subarray and adding the smaller one to the resulting array, until both subarrays are empty.

Merge sort is stable (preserves the relative order of equal elements) and has a guaranteed time complexity of O(n log n) in the worst, average, and best cases. However, it requires additional O(n) memory for temporary storage during merging.

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

    # Divide the array in half
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort the subarrays
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Merge the sorted subarrays
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0

    # Merge elements in sorted order
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    # Add remaining elements, if any
    result.extend(left[left_index:])
    result.extend(right[right_index:])

    return result

# Example usage
# unsorted_array = [38, 27, 43, 3, 9, 82, 10]
# sorted_array = merge_sort(unsorted_array)
# print(sorted_array)