16 Recursive Sorting

1. Split up the input into two or more parts.
2. Recurse on each part separately.
3. Combine the results of the previous step into a single result

Mergesort

def mergesort(lst: list) -> list:
	"""Return a sorted list with the same elements as <lst>.
		This is a *non-mutating* version of mergesort; it does not mutate the input list.
	"""
	if len(lst) < 2:
		return lst[:]
	else: 
		mid = len(lst) // 2
		left_sorted = mergesort(lst[:mid])
		right_sorted = mergesort(lst[mid:])

		return _merge(left_sorted, right_sorted)

def _merge(lst1: list, lst2: lst) -> list:
	"""Return a sorted list with elements in <lst1> and <lst2>.
	Precondition: <lst1> and <lst2> are sorted
	"""
	index1 = 0
	index2 = 0 
	merged = []

	while index1 < len(lst1) and index2 < len(lst2):
		if lst1[index1] <= lst2[index2]:
			merged.append(lst1[index1])
			index1 += 1
		else: 
			merged.append(lst2[index2])
			index2+=1
			
	return merged + lst1[index1:] + lst2[index2:] # at most one is non-empty

The efficiency is $\mathcal{O}(n\log n)$ since we run the algorithm of $n$ items which are subdivided in halves.

Quicksort

1. First, it picks some element in its input list and calls it the pivot.
2. It then splits up the list into two parts: the elements less than or equal to the pivot, and those greater than the pivot. This is traditionally called the partitioning step.
3. Next, it sorts each part recursively.
4. Finally, it concatenates the two sorted parts, putting the pivot in between them.

def quicksort(lst: list) -> list: 

	if len(lst) < 2: 
		return lst[:]
	else:
		pivot = lst[0]
		smaller, bigger = _partition(lst[1:], pivot)
	smaller_sorted = quicksort(smaller)
	bigger_sorted = quicksort(bigger)

	return smaller_sorted + [pivot] + bigger_sorted

def _partition(lst: list, pivot: Any) -> tuple[list, list]:
	bigger = []
	smaller = []

	for item in lst: 
		it item <= pivot: 
			smaller.append(item)
		else: 
			bigger.append(item)
	return smaller, bigger

if every case the pivot is the lowest then we have $\mathcal{O}(n^2)$ otherwise if we choose a pivot at random we get $\mathcal{O}(n\log n)$ on average

In Place Quicksort

def _in_place_partition(lst: list[int], start: int, end: int) -> int:
    # Set the pivot as the first element in the range
    pivot = lst[start]
    small_i = start + 1  # Start just after the pivot
    big_i = end  # End is the last index in the range

    while small_i <= big_i:
        # Move small_i forward until we find an element > pivot
        if lst[small_i] <= pivot:
            small_i += 1
        # Move big_i backward until we find an element <= pivot
        elif lst[big_i] > pivot:
            big_i -= 1
        else:
            # Swap elements at small_i and big_i
            lst[small_i], lst[big_i] = lst[big_i], lst[small_i]
            small_i += 1
            big_i -= 1

    # After the loop, small_i is where the pivot should be placed
    # Swap the pivot into its correct position
    lst[start], lst[big_i] = lst[big_i], lst[start]
    # Return the new index of the pivot
    return big_i

def quicksort(lst: list[int], start: int, end: int) -> None:
    if start < end:
        # Partition the list and get the pivot index
        pivot_index = _in_place_partition(lst, start, end)
        # Recursively sort the left and right sublists
        quicksort(lst, start, pivot_index - 1)  # Left side
        quicksort(lst, pivot_index + 1, end)    # Right side