How to Sort a List Recursively in Python

To sort a list recursively in Python, you can use a divide-and-conquer approach like merge sort or quicksort. Both of these algorithms work by dividing the original input list into two smaller sub-lists, recursively sorting each sub-list, and then merging or combining the results to produce the sorted final list.

Here’s an example of how to use a recursive merge sort function to sort a list in Python:

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

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)

    return merge(left_sorted, right_sorted)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]
    return result

# Sample usage
arr = [3, 2, 1, 5, 4]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4, 5]

In this example, the merge_sort() function takes an input list arr and recursively splits it into two smaller sub-lists until it reaches a base case where the sub-list has only one element. Then it calls the merge() function to combine the sorted sub-lists back together in the correct order.

There are other recursive sorting algorithms that you can use, such as quicksort or recursive insertion sort, but the basic approach is similar. You can also use Python’s built-in sorted() function to sort a list, which uses a variant of merge sort.