Sorting Algorithms

Here are some good sorting algorithms to know about. You can learn about their complexity in a full comparison here.

Quick Sort

Algorithm

• Choose a pivot (first, mid or last)
• Put the numbers smaller than the pivot in a new left array
• Put the numbers larger than the pivot in a new right array
• Recursively sort the left and right arrays
• Return the combined array of left + [pivot] + right

Complexity

Implementation

def quicksort(nums):
	if len(nums) <= 1:
		return nums

	left, right = [], []
	pivot = nums.pop()

	for n in nums:
		if n <= pivot:
			left.append(n)
		else:
			right.append(n)
	return quicksort(left) + [pivot] + quicksort(right)

Merge Sort

Complexity

Algorithm # 1

• Split the array into two
• Sort the left array and the right array
• Merge them together

def mergesort(nums):
    if len(nums) <= 1:
        return nums
    left, right = nums[0:len(nums) // 2], nums[len(nums) // 2: len(nums)]
    
    sortedLeft = mergesort(left)
    sortedRight = mergesort(right)

    i = j = 0

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

    result.extend(sortedLeft[i:])
    result.extend(sortedRight[j:])
    return result

Algorithm # 2

• mergeSort() is initially called
• Sort the two halves of the array
• Merge them in place
• [[#Algorithm 2]] is more efficient because it does not create a separate array for each call stack. It only creates new arrays while merging.

def sortArray(self, nums: List[int]) -> List[int]:    
	
	# Merge two sorted halves into the original array
	def merge(arr, L, R):
		mid = L + (R - L) // 2
		left, right = arr[L:mid + 1], arr[mid + 1:R + 1]
		i = j = 0
		r = L

		# Merge left and right arrays
		while i < len(left) and j < len(right):
			if left[i] < right[j]:
				arr[r] = left[i]
				i += 1
			else:
				arr[r] = right[j]
				j += 1
			r += 1
		
		# Add remaining elements from left
		while i < len(left):
			arr[r] = left[i]
			i += 1
			r += 1
		
		# Add remaining elements from right
		while j < len(right):
			arr[r] = right[j]
			j += 1
			r += 1
	
	# Recursive merge sort function
	def mergeSort(arr, L, R):
		if L < R:
			mid = L + (R - L) // 2
			mergeSort(arr, L, mid)
			mergeSort(arr, mid + 1, R)
			merge(arr, L, R)
	
	mergeSort(nums, 0, len(nums) - 1)
	return nums