Sorting & Graph Algorithms
A Practical Reference Guide with Pseudocode, Complexity Analysis, and Use Cases
This guide walks through the core sorting and graph algorithms every developer should know cold: how each
one works, its pseudocode, and when to reach for it over the alternatives. Sorting algorithms are covered first
— from simple O(n²) approaches to the O(n log n) workhorses used in production systems — followed by the
fundamental graph traversal and shortest-path/minimum-spanning-tree algorithms that power everything from
routing to dependency resolution.
Section Topics Page
1. Sorting Algorithms Bubble, Selection, Insertion Sort 2
2. Sorting Algorithms Merge Sort, Quick Sort 3
3. Sorting Algorithms Heap Sort & Complexity Comparison 4
4. Graph Basics Representations (Adjacency List/Matrix) 5
5. Graph Traversal BFS & DFS 6
6. Shortest Path Dijkstra's Algorithm 7
7. Minimum Spanning Tree Prim's & Kruskal's Algorithm 8
8. Ordering Topological Sort 9
9. Summary Complexity Cheat Sheet & When to Use What 10
1. Sorting Algorithms — Simple Methods
These three algorithms are the starting point for learning sorting. They are easy to understand and implement,
but their O(n²) worst-case time complexity makes them impractical for large datasets. They remain useful for
small inputs, nearly-sorted data, or teaching purposes.
Bubble Sort
Repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong
order. Each pass 'bubbles' the largest unsorted element to its correct position at the end.
function bubbleSort(arr):
n = length(arr)
for i from 0 to n-1:
swapped = false
for j from 0 to n-i-2:
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])
swapped = true
if not swapped:
break # array already sorted, exit early
return arr
Selection Sort
Divides the array into a sorted and unsorted region. On each pass, it finds the minimum element in the unsorted
region and swaps it into place at the boundary. It performs the minimum possible number of swaps (n-1), which
is useful when write operations are costly.
function selectionSort(arr):
n = length(arr)
for i from 0 to n-1:
minIdx = i
for j from i+1 to n-1:
if arr[j] < arr[minIdx]:
minIdx = j
swap(arr[i], arr[minIdx])
return arr
Insertion Sort
Builds the sorted array one element at a time by taking each new element and inserting it into its correct
position among the already-sorted elements. It performs very well on nearly-sorted or small datasets and is
used internally by hybrid algorithms like Timsort for small partitions.
function insertionSort(arr):
for i from 1 to length(arr)-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = key
return arr
2. Sorting Algorithms — Divide and Conquer
Merge Sort and Quick Sort both use a divide-and-conquer strategy to achieve O(n log n) average performance,
making them the practical choice for large datasets.
Merge Sort
Recursively splits the array in half until each sub-array has one element, then merges sub-arrays back together
in sorted order. It guarantees O(n log n) in the worst case and is stable, but requires O(n) extra space for the
merge step.
function mergeSort(arr):
if length(arr) <= 1:
return arr
mid = length(arr) / 2
left = mergeSort(arr[0:mid])
right = mergeSort(arr[mid:end])
return merge(left, right)
function merge(left, right):
result = []
i = j = 0
while i < length(left) and j < length(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result
Quick Sort
Picks a 'pivot' element and partitions the array so smaller elements come before it and larger ones after, then
recursively sorts each partition. It's typically faster in practice than Merge Sort due to good cache locality and
in-place partitioning, though its worst case degrades to O(n²) with a poor pivot choice.
function quickSort(arr, low, high):
if low < high:
pivotIndex = partition(arr, low, high)
quickSort(arr, low, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, high)
function partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j from low to high-1:
if arr[j] <= pivot:
i = i + 1
swap(arr[i], arr[j])
swap(arr[i+1], arr[high])
return i + 1
3. Sorting Algorithms — Heap Sort & Comparison
Heap Sort
Builds a max-heap from the input data, then repeatedly extracts the maximum element and rebuilds the heap. It
guarantees O(n log n) in all cases and sorts in place, though it is not stable and has weaker cache performance
than Quick Sort.
function heapSort(arr):
n = length(arr)
buildMaxHeap(arr, n)
for i from n-1 downto 1:
swap(arr[0], arr[i]) # move current max to the end
heapify(arr, i, 0) # restore heap property on shrunk heap
return arr
function heapify(arr, n, i):
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and arr[left] > arr[largest]: largest = left
if right < n and arr[right] > arr[largest]: largest = right
if largest != i:
swap(arr[i], arr[largest])
heapify(arr, n, largest)
Sorting Algorithm Complexity Comparison
Algorithm Best Average Worst Space / Stability
Bubble Sort O(n) O(n²) O(n²) O(1) / Stable
Selection Sort O(n²) O(n²) O(n²) O(1) / Not Stable
Insertion Sort O(n) O(n²) O(n²) O(1) / Stable
Merge Sort O(n log n) O(n log n) O(n log n) O(n) / Stable
Quick Sort O(n log n) O(n log n) O(n²) O(log n) / Not Stable
Heap Sort O(n log n) O(n log n) O(n log n) O(1) / Not Stable
Rule of thumb: use Insertion Sort for small or nearly-sorted inputs, Merge Sort when stability and guaranteed
O(n log n) matter, and Quick Sort for general-purpose in-memory sorting where average-case speed is the
priority.
4. Graph Basics — Representation
A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Graphs may
be directed or undirected, and weighted or unweighted. The two most common ways to represent a graph in
code are the adjacency list and the adjacency matrix, and the right choice depends on graph density and the
operations you need to support.
Adjacency List
Stores, for each vertex, a list of its neighboring vertices. This is space-efficient for sparse graphs, using O(V +
E) memory, and is the representation used by nearly all the algorithms in this guide.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
# Weighted version stores (neighbor, weight) pairs:
graph = {
'A': [('B', 4), ('C', 1)],
'B': [('A', 4), ('D', 2)],
...
}
Adjacency Matrix
A V x V matrix where cell [i][j] holds the edge weight (or 1/0) between vertex i and vertex j. Edge lookups are
O(1), but the matrix uses O(V²) space regardless of how many edges actually exist, so it suits dense graphs
better than sparse ones.
A B C D E
A [ 0, 1, 1, 0, 0 ]
B [ 1, 0, 0, 1, 0 ]
C [ 1, 0, 0, 1, 0 ]
D [ 0, 1, 1, 0, 1 ]
E [ 0, 0, 0, 1, 0 ]
Representation Space Edge Lookup Add Edge Best For
Adjacency List O(V + E) O(V) O(1) amortized Sparse graphs
Adjacency Matrix O(V²) O(1) O(V) Dense graphs
5. Graph Traversal — BFS & DFS
Breadth-First Search and Depth-First Search are the two fundamental strategies for visiting every vertex in a
graph. Both run in O(V + E) time using an adjacency list.
Breadth-First Search (BFS)
Explores the graph level by level using a queue, visiting all neighbors of a vertex before moving to the next
level. BFS finds the shortest path in terms of edge count on unweighted graphs.
function BFS(graph, start):
visited = set([start])
queue = [start]
order = []
while queue is not empty:
vertex = [Link]()
[Link](vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return order
Depth-First Search (DFS)
Explores as far as possible along each branch using a stack (or recursion) before backtracking. DFS is well
suited to cycle detection, topological sorting, and connected-component analysis.
function DFS(graph, start, visited=set()):
[Link](start)
order = [start]
for neighbor in graph[start]:
if neighbor not in visited:
[Link](DFS(graph, neighbor, visited))
return order
# Iterative version using an explicit stack:
function DFS_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack is not empty:
vertex = [Link]()
if vertex not in visited:
[Link](vertex)
[Link](vertex)
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
[Link](neighbor)
return order
6. Shortest Path — Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source vertex to every other vertex in a weighted graph
with non-negative edge weights. It greedily selects the closest unvisited vertex at each step, using a min-priority
queue to run in O((V + E) log V) time.
function dijkstra(graph, start):
dist = {v: infinity for v in graph}
dist[start] = 0
pq = MinPriorityQueue()
[Link]((0, start))
while pq is not empty:
(currentDist, u) = [Link]()
if currentDist > dist[u]:
continue # stale entry, skip
for (v, weight) in graph[u]:
newDist = currentDist + weight
if newDist < dist[v]:
dist[v] = newDist
[Link]((newDist, v))
return dist
Because it relies on greedily fixing the shortest distance once a vertex is popped, Dijkstra's algorithm does not
work correctly with negative edge weights — the Bellman-Ford algorithm should be used instead in that case, at
the cost of a slower O(V · E) running time.
Worked Example
Given edges A-B (4), A-C (1), C-B (2), B-D (5), C-D (8), starting from A: the algorithm first fixes dist(A)=0, then
dist(C)=1 (via A), then dist(B)=3 (via A→C→B, cheaper than the direct A→B edge of 4), and finally dist(D)=8
(via A→C→B→D).
7. Minimum Spanning Tree — Prim's & Kruskal's
A Minimum Spanning Tree (MST) connects all vertices of a weighted, undirected graph with the minimum
possible total edge weight and no cycles. Prim's and Kruskal's are the two classic algorithms for computing it,
both provably optimal via the greedy choice property.
Prim's Algorithm
Grows the MST one vertex at a time, always adding the cheapest edge that connects a vertex already in the
tree to one that isn't. Using a min-heap, it runs in O(E log V) time — well suited to dense graphs.
function prim(graph, start):
inMST = set([start])
mstEdges = []
pq = MinPriorityQueue()
for (v, weight) in graph[start]:
[Link]((weight, start, v))
while pq is not empty and length(inMST) < length(graph):
(weight, u, v) = [Link]()
if v in inMST:
continue
[Link](v)
[Link]((u, v, weight))
for (next_v, w) in graph[v]:
if next_v not in inMST:
[Link]((w, v, next_v))
return mstEdges
Kruskal's Algorithm
Sorts all edges by weight and adds them one at a time, skipping any edge that would form a cycle, using a
Union-Find (disjoint-set) structure to detect cycles in near constant time. Overall complexity is O(E log E), which
is dominated by the sort.
function kruskal(vertices, edges):
sort edges by weight ascending
unionFind = UnionFind(vertices)
mstEdges = []
for (u, v, weight) in edges:
if [Link](u) != [Link](v):
[Link](u, v)
[Link]((u, v, weight))
return mstEdges
8. Ordering — Topological Sort
A topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every
directed edge u → v, u comes before v in the ordering. It is used for task scheduling, build systems, and
course-prerequisite resolution. A topological order only exists if the graph has no cycles.
Kahn's Algorithm (BFS-based)
Repeatedly removes vertices with in-degree zero, adding them to the result and decrementing the in-degree of
their neighbors. If any vertices remain when the queue empties, the graph contains a cycle.
function topologicalSortKahn(graph):
inDegree = {v: 0 for v in graph}
for u in graph:
for v in graph[u]:
inDegree[v] += 1
queue = [v for v in graph if inDegree[v] == 0]
order = []
while queue is not empty:
u = [Link]()
[Link](u)
for v in graph[u]:
inDegree[v] -= 1
if inDegree[v] == 0:
[Link](v)
if length(order) != length(graph):
raise Error("Graph has a cycle")
return order
DFS-based Approach
Runs DFS and pushes each vertex onto a stack after all its descendants have been visited; reversing the stack
at the end gives a valid topological order. Both approaches run in O(V + E) time.
function topologicalSortDFS(graph):
visited = set()
stack = []
for v in graph:
if v not in visited:
dfsVisit(graph, v, visited, stack)
return reverse(stack)
function dfsVisit(graph, v, visited, stack):
[Link](v)
for neighbor in graph[v]:
if neighbor not in visited:
dfsVisit(graph, neighbor, visited, stack)
[Link](v)
9. Summary — Complexity Cheat Sheet
Graph Algorithm Complexity
Algorithm Time Space Typical Use Case
BFS O(V + E) O(V) Shortest path (unweighted), level order
DFS O(V + E) O(V) Cycle detection, connectivity, backtracking
Dijkstra's O((V+E) log V) O(V) Shortest path, non-negative weights
Prim's (MST) O(E log V) O(V) MST on dense graphs
Kruskal's (MST) O(E log E) O(V) MST on sparse graphs
Topological Sort O(V + E) O(V) Task scheduling, dependency resolution
When to Use What
Sorting: Use Insertion Sort for tiny or nearly-sorted arrays, Merge Sort when stability and worst-case
guarantees matter (e.g. external sorting, linked lists), and Quick Sort or Heap Sort for general in-memory
sorting where average speed or in-place space usage is the priority.
Graphs: Use BFS for shortest paths on unweighted graphs and level-order problems, DFS for exploring
structure and detecting cycles, Dijkstra's for weighted shortest paths with non-negative weights, Prim's or
Kruskal's for building a minimum spanning network, and Topological Sort whenever a task has ordering
dependencies.
This reference guide covers the algorithmic foundations most commonly tested in technical interviews and used
in real-world systems design. For implementation in a specific language, the pseudocode above maps directly
onto Python, Java, C++, or JavaScript with minimal changes.