# Title: Merge sort
# Heading: Python Program for Merge Sort
# Level: intermediate
# Tags: sorting, merge sort, divide and conquer, recursion
# Time: O(n log n)
# Space: O(n)
# About: Sorts a list by splitting it in half, sorting each half the same way, then merging the two sorted halves into one.

def merge_sort(items):
    """Return the items sorted from smallest to largest."""
    if len(items) <= 1:
        return items
    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])
    return merge(left, right)


def merge(left, right):
    """Merge two sorted lists into one sorted list."""
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # One list is used up: the rest of the other is already sorted
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
print("After: ", merge_sort(numbers))