Sorting Algorithms Cheat Sheet

Compares common sorting algorithms by time and space complexity and stability, with runnable merge sort and quicksort implementations.

2 PagesIntermediateMar 22, 2026

Algorithm Comparison

Time complexity, space complexity, and stability at a glance.

Bubble Sort- O(n^2) time, O(1) space, stable; repeatedly swaps adjacent out-of-order elements
Insertion Sort- O(n^2) worst case but O(n) on nearly-sorted data, O(1) space, stable; good for small or almost-sorted arrays
Selection Sort- O(n^2) time, O(1) space, not stable; repeatedly selects the minimum remaining element
Merge Sort- O(n log n) time guaranteed, O(n) space, stable; divide-and-conquer, good for linked lists and external sorting
Quicksort- O(n log n) average, O(n^2) worst case, O(log n) space, not stable; fast in practice due to cache locality
Heapsort- O(n log n) time guaranteed, O(1) space, not stable; builds a heap then repeatedly extracts the max

Merge Sort

Classic divide-and-conquer sort with guaranteed O(n log n).

python

def merge_sort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left = merge_sort(arr[:mid])    right = merge_sort(arr[mid:])    return merge(left, right)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.extend(left[i:])    result.extend(right[j:])    return result

Quicksort

Fast average-case sort using a pivot and partitioning.

python

def quick_sort(arr):    if len(arr) <= 1:        return arr    pivot = arr[len(arr) // 2]    left = [x for x in arr if x < pivot]    mid = [x for x in arr if x == pivot]    right = [x for x in arr if x > pivot]    return quick_sort(left) + mid + quick_sort(right)

Using Built-in Sort

Python's Timsort with custom keys.

python

# Python's sort is Timsort (hybrid merge/insertion sort),# O(n log n) worst case, and stablenums = [5, 2, 8, 1]sorted(nums)                          # returns new list, ascendingnums.sort(reverse=True)               # in-place, descending# Sorting with a custom keywords = ["banana", "kiwi", "apple"]sorted(words, key=len)                # by length: ['kiwi', 'apple', 'banana']sorted(words, key=lambda w: w[::-1])  # by reversed string

Pro Tip

Reach for the language's built-in sort (Timsort in Python, Collections.sort in Java, introsort in C++'s std::sort) instead of hand-rolling one — they're heavily optimized and, for Python/Java, stable by default.

Was this cheat sheet helpful?

Recursion Cheat Sheet

Searching Algorithms Cheat Sheet

Explore Topics

#SortingAlgorithms#SortingAlgorithmsCheatSheet#Programming#Intermediate#AlgorithmComparison#MergeSort#Quicksort#UsingBuiltInSort#Algorithms#Git#CheatSheet#SkillVeris

Sri Hayavadhana Info-Tech

Professional Web Designing Services