Sorting Patterns

Merge Sort

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
 
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)
 
def merge(left, right):
    i=j=0
    out = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend[left[i:]]
    out.extend(right[j:])
    

Custom comparable

Either invent a key to sort by:

intervals.sort(key=lambda x: (x[0], x[1]))

or create a comparable function:

def compare(a, b):
	if (a+b) > (b+a):
		return -1
		
	if (a+b) < (b+a):
		return 1
	return 0
	
arr.sort(key=cmp_to_key(compare))

Cyclic sort

def cyclic_sort(nums):
	i, n = 0, len(nums)
	while i < n:
		j = nums[i] - 1 # home index
		if nums[i] != nums[j]: # not in place
			nums[i], nums[j] = nums[j], nums[i]
		else:
			i+=1
			
	return nums
 

Next Permutation

def next_permutation(a):
	"""
	find the rightmost ascent, swap with the next larger suffix value, then reverse the suffix
	"""
	n = len(a)
	i = n-2
	while i>=0 and a[i] >= a[i+1]:
		i-=1
	if i >= 0:
		j = n-1
		while a[j] <= a[i]:
			j-=1
		a[i], a[j] = a[j], a[i]
	a[i + 1 :] = reversed(a[i + 1 :])