I want to explain partitioning as one of the more general and widely reused ideas in computer science and operations research: the problem of dividing a set of items, a graph, or a dataset into distinct, non-overlapping groups (partitions) that satisfy some optimality or balance criterion. I find it important because it underlies everything from the “divide” step of divide-and-conquer sorting algorithms, to graph partitioning for parallel computing, to balanced workload assignment in distributed systems.
History and Background
Partitioning as a mathematical idea traces back to combinatorics and number theory (the study of integer partitions goes back to Euler in the 18th century), but the algorithmic partitioning I focus on here — set/graph partitioning for optimization — became prominent in the mid-20th century alongside the growth of operations research and computer science. Tony Hoare’s Quicksort (1960) popularized the partition step as a core algorithmic primitive, while graph partitioning as an optimization problem was formalized in the 1970s, with the Kernighan–Lin algorithm (1970) becoming one of the most influential heuristic methods for balanced graph partitioning, later refined by Fiduccia and Mattheyses in 1982.
Problem Statement
I describe the general partitioning problem as: given a set $S$ (or a graph $G$), divide it into $k$ disjoint subsets $S_1, S_2, \dots, S_k$ such that $\bigcup_i S_i = S$ and $S_i \cap S_j = \emptyset$ for $i \neq j$, while optimizing some objective — commonly minimizing the “cost” of the partition (e.g., edges cut between subsets in graph partitioning, or the difference between subset sums in number partitioning) subject to balance constraints (e.g., roughly equal subset sizes).
Core Concepts
- Partition: a division of a set into non-overlapping, exhaustive subsets.
- Balanced partition: a partition where the subsets are approximately equal in size or weight.
- Cut size: in graph partitioning, the number (or total weight) of edges that cross between different subsets — the quantity I typically want to minimize.
- Pivot: in the Quicksort-style partitioning routine, the reference element used to split a list into “less than” and “greater than” groups.
- Load balancing: ensuring that each partition carries roughly equal computational or storage burden, common in distributed systems.
How It Works
I’ll describe the two most common forms I encounter:
A. Quicksort-style array partitioning (Lomuto scheme):
- I choose a pivot element, often the last element of the array segment.
- I maintain an index marking the boundary of elements known to be smaller than the pivot.
- I scan through the array; whenever I find an element smaller than the pivot, I swap it into the boundary region and advance the boundary index.
- At the end, I swap the pivot into its correct final position, which now separates the “smaller” and “larger” groups.
B. Graph/set partitioning (Kernighan–Lin style):
- I start with an initial partition (often random or based on natural ordering) into two roughly equal-sized groups.
- I compute the gain of swapping each pair of nodes (one from each group) — the reduction in cut size that swap would produce.
- I repeatedly perform the swap with the highest gain, locking the swapped nodes so they aren’t moved again in this pass.
- After all nodes are locked, I look back at the sequence of swaps and pick the prefix that gave the greatest cumulative cut reduction.
- I repeat these passes until no further improvement is found.
Working Principle
The underlying logic in both cases is a form of local, incremental refinement guided by a well-defined objective function. In the array case, the objective is “is this element on the correct side of the pivot,” resolved through a single linear scan. In the graph case, the logic is a greedy local search: I always take the locally best-looking move, but I allow temporarily “bad” moves within a pass (since gains can go negative before rising again) so that the algorithm can escape shallow local optima — this is the key insight that separates Kernighan–Lin from naive greedy swapping.
Mathematical Foundation
For array partitioning around pivot $p$, correctness after processing requires:
$$ \forall i < \text{pivot index}: A[i] \leq p \quad \text{and} \quad \forall i > \text{pivot index}: A[i] > p $$
For graph partitioning into two balanced sets $A$ and $B$, I define the cut size as:
$$ \text{cut}(A,B) = \sum_{i \in A, j \in B} w_{ij} $$
where $w_{ij}$ is the edge weight between nodes $i$ and $j$. The objective is:
$$ \min_{A,B} \ \text{cut}(A,B) \quad \text{subject to} \quad \big| |A| – |B| \big| \leq 1 $$
For the gain-based swap used in Kernighan–Lin, the gain $g$ of swapping node $a \in A$ with node $b \in B$ is:
$$ g(a,b) = D(a) + D(b) – 2 w_{ab} $$
where $D(x)$ is the difference between external and internal edge costs of node $x$.
Diagrams
flowchart TD
Start([Start: initial partition]) --> Gain[Compute swap gains for all pairs]
Gain --> Best[Select and apply best-gain swap, lock nodes]
Best --> More{Unlocked nodes remain?}
More -- Yes --> Gain
More -- No --> Prefix[Find prefix of swap sequence with max cumulative gain]
Prefix --> Apply[Apply that prefix permanently]
Apply --> Improve{Improvement found this pass?}
Improve -- Yes --> Start
Improve -- No --> End([Return final partition])Pseudocode
Array partition (Lomuto scheme):
function Partition(A, low, high):
pivot = A[high]
i = low - 1
for j from low to high - 1:
if A[j] <= pivot:
i = i + 1
swap(A[i], A[j])
swap(A[i+1], A[high])
return i + 1 // final pivot index
Graph partition (Kernighan–Lin, simplified):
function KernighanLin(Graph, A, B):
improved = true
while improved:
improved = false
unlocked = all nodes
gains = []
while unlocked is not empty:
(a, b) = pair in A x B with max gain(a, b)
record swap(a, b) and its gain
lock a, b
update gains of remaining unlocked nodes
find prefix of recorded swaps with maximum cumulative gain
if that cumulative gain > 0:
apply the swaps in that prefix to A, B
improved = true
return A, B
Step-by-Step Example
Array partition example: Array = [8, 3, 5, 1, 9, 2], pivot = 2 (last element).
- i starts at −1.
- j=0 (8): 8 > 2, skip.
- j=1 (3): 3 > 2, skip.
- j=2 (5): 5 > 2, skip.
- j=3 (1): 1 ≤ 2, i=0, swap A[0] and A[3] → [1, 3, 5, 8, 9, 2].
- j=4 (9): 9 > 2, skip.
- Swap A[i+1]=A[1] with A[5] (pivot) → [1, 2, 5, 8, 9, 3].
- Final pivot index = 1. Left partition: [1]. Right partition: [5, 8, 9, 3].
Time Complexity
- Array (Quicksort) partitioning: $O(n)$ per partition call, best/average case overall sort $O(n \log n)$, worst case $O(n^2)$ when pivots are consistently poor (e.g., already-sorted input with last-element pivoting).
- Kernighan–Lin graph partitioning: each pass is $O(n^2 \log n)$ or $O(n^3)$ depending on implementation, since I recompute gains after each locked swap; multiple passes are typically needed until convergence.
Space Complexity
- Array partitioning: $O(1)$ additional space (in-place), plus $O(\log n)$ recursion stack space for the surrounding Quicksort.
- Graph partitioning: $O(n^2)$ if I store a full weighted adjacency matrix, or $O(n+E)$ with an adjacency list, plus $O(n)$ for gain tracking and locking state.
Correctness Analysis
For array partitioning, correctness follows directly from the loop invariant: at the start of each iteration, all elements in $A[low..i]$ are $\leq$ pivot, and all elements in $A[i+1..j-1]$ are $>$ pivot; this invariant is maintained by the swap logic and, upon loop termination, guarantees the pivot lands in its correct sorted position. For Kernighan–Lin partitioning, there is no guarantee of a globally optimal cut (the problem is NP-hard in general), but each pass is guaranteed to never increase the cut size, since I only keep the prefix of swaps with positive cumulative gain — so the algorithm converges monotonically to a local optimum.
Advantages
- Array partitioning is simple, in-place, and forms the backbone of efficient sorting and selection algorithms (Quicksort, Quickselect).
- Graph/set partitioning heuristics like Kernighan–Lin can escape shallow local minima by allowing temporarily negative-gain moves within a pass.
- Partitioning generalizes well — the same idea underlies load balancing, parallel processing task division, and database sharding.
Disadvantages
- Array partitioning’s worst-case performance depends heavily on pivot choice; poor pivots degrade performance to $O(n^2)$.
- Graph partitioning is NP-hard in general, so heuristic methods like Kernighan–Lin only guarantee local optimality, not global.
- Balanced partitioning of highly irregular or skewed data can be difficult to achieve without sacrificing the optimization objective.
Applications
- Sorting and selection algorithms (Quicksort, Quickselect, median-finding).
- VLSI circuit design, where graph partitioning minimizes wire connections between chip regions.
- Parallel and distributed computing, dividing workloads or graphs across processors to minimize communication overhead.
- Database sharding and distributed storage design.
- Community detection in social network analysis.
Implementation in C
#include <stdio.h>
// Swap two integers
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// Lomuto partition scheme
int partition(int A[], int low, int high) {
int pivot = A[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (A[j] <= pivot) {
i++;
swap(&A[i], &A[j]);
}
}
swap(&A[i + 1], &A[high]);
return i + 1;
}
void quicksort(int A[], int low, int high) {
if (low < high) {
int pi = partition(A, low, high);
quicksort(A, low, pi - 1);
quicksort(A, pi + 1, high);
}
}
int main() {
int A[] = {8, 3, 5, 1, 9, 2};
int n = sizeof(A) / sizeof(A[0]);
quicksort(A, 0, n - 1);
printf("Partitioned/sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
return 0;
}
Sample Input and Output
Input: Array = [8, 3, 5, 1, 9, 2]
Output:
Partitioned/sorted array: 1 2 3 5 8 9
The single partition step I traced by hand corresponds to the first level of recursion here; the full quicksort continues partitioning each side until the array is sorted.
Optimization Techniques
- Use median-of-three pivot selection (comparing the first, middle, and last elements) to avoid worst-case behavior on sorted or reverse-sorted input.
- Switch to insertion sort for small sub-arrays (below roughly 10–20 elements) to reduce recursion overhead.
- For graph partitioning, use multilevel approaches (like METIS) that coarsen the graph first, partition the small version, then refine back up — much faster than running Kernighan–Lin directly on a large graph.
- Parallelize independent partition/gain computations across multiple threads for large datasets.
Common Mistakes
- Choosing a fixed pivot (like always the first or last element) on data that is already sorted, causing worst-case $O(n^2)$ behavior.
- Off-by-one errors in the partition boundary index, leading to incorrect element placement.
- In graph partitioning, forgetting to lock swapped nodes, which can cause infinite oscillation between two states.
- Assuming a locally optimal partition from Kernighan–Lin is globally optimal — it generally is not, since the underlying problem is NP-hard.
Further Reading
- Hoare, C. A. R. (1962). “Quicksort.” The Computer Journal, 5(1), 10–16.
- Kernighan, B. W., & Lin, S. (1970). “An Efficient Heuristic Procedure for Partitioning Graphs.” Bell System Technical Journal, 49(2), 291–307.
- Fiduccia, C. M., & Mattheyses, R. M. (1982). “A Linear-Time Heuristic for Improving Network Partitions.” 19th Design Automation Conference.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- METIS graph partitioning documentation: https://github.com/KarypisLab/METIS
