Sorting is everywhere because sorted data is easy to process. Duplicates end up next to each other, the most frequent value forms the longest run, and binary search becomes possible. Efficient sorting takes O(n log n), so many algorithms that sort first are O(n log n) too.
Sorting har jagah hai kyunki sorted data ke saath kaam aasaan hota hai: duplicates ek saath aa jaate hain, sabse frequent value sabse lambi run banti hai, aur binary search possible ho jaata hai. Efficient sorting O(n log n) leta hai, isliye jo algorithms pehle sort karte hain woh bhi aksar O(n log n) hote hain.
3.1Sorting theory
O(n²): bubble sort and inversions
Bubble sort makes n rounds, and each round swaps every neighbouring pair that’s out of order. After k rounds, the k largest values are in place.
An inversion is a pair (i, j) with i < j but a[i] > a[j]. [1, 2, 2, 6, 3, 5, 9, 8] has three: (6,3), (6,5) and (9,8). Swapping two neighbours removes exactly one inversion. A reversed array has n(n−1)/2 inversions, so any sort that only swaps neighbours is O(n²).
Bubble sort n rounds chalta hai; har round mein galat order wale har padosi pair ko swap karta hai. k rounds ke baad k sabse badi values apni jagah pe hoti hain.
Inversion ek pair (i, j) hai jahan i < j par a[i] > a[j]. [1, 2, 2, 6, 3, 5, 9, 8] mein teen hain: (6,3), (6,5), (9,8). Do padosiyon ka swap theek ek inversion hatata hai, aur reversed array mein n(n−1)/2 inversions hote hain — isliye sirf padosi swap karne wala koi bhi sort O(n²) hai.
static void bubbleSort(int[] a) { int n = a.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } }}O(n log n): merge sort
Merge sort splits the range in half, sorts each half recursively, then merges the two sorted halves in linear time by repeatedly taking the smaller front element. There are about log₂ n levels of halving and each level does O(n) work, so the total is O(n log n).
Merge sort range ko aadha karta hai, dono halves ko recursively sort karta hai, phir dono sorted halves ko linear time mein merge karta hai — baar baar aage wale do elements mein se chhota utha ke. Halving ke lagbhag log₂ n levels hain aur har level O(n) kaam karta hai: total O(n log n).
static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length - 1);} /** Sorts a[lo..hi]; tmp is scratch space so we allocate only once. */static void mergeSort(int[] a, int[] tmp, int lo, int hi) { if (lo >= hi) return; int mid = (lo + hi) >>> 1; mergeSort(a, tmp, lo, mid); mergeSort(a, tmp, mid + 1, hi); int i = lo, j = mid + 1, k = lo; while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i <= mid) tmp[k++] = a[i++]; while (j <= hi) tmp[k++] = a[j++]; System.arraycopy(tmp, lo, a, lo, hi - lo + 1);}- left half / region
- right half / compared
- current
- just written
- in final place
Merge sort: split the range in half, sort both halves recursively, then merge the two sorted halves in linear time.
static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length - 1);} /** Sorts a[lo..hi]; tmp is scratch space so we allocate only once. */static void mergeSort(int[] a, int[] tmp, int lo, int hi) { if (lo >= hi) return; int mid = (lo + hi) >>> 1; mergeSort(a, tmp, lo, mid); mergeSort(a, tmp, mid + 1, hi); int i = lo, j = mid + 1, k = lo; while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i <= mid) tmp[k++] = a[i++]; while (j <= hi) tmp[k++] = a[j++]; System.arraycopy(tmp, lo, a, lo, hi - lo + 1);}The lower bound, and counting sort
No sort that works only by comparing elements can beat O(n log n). There are n! possible orders, and each comparison has two outcomes, so you need at least log₂(n!) ≥ (n/2)·log₂(n/2) comparisons. That bound only applies to comparison sorts. Counting sort never compares. For values in 0..c, it counts each value in an array of size c + 1, then writes the values out in order, for O(n + c) total. That’s linear when c = O(n).
Jo sort sirf elements ko compare karke kaam karta hai, woh O(n log n) se tez nahi ho sakta. n! possible orders hain aur har comparison ke do hi results, toh kam se kam log₂(n!) ≥ (n/2)·log₂(n/2) comparisons chahiye. Yeh limit sirf comparison sorts pe hai. Counting sort compare karta hi nahi: values 0..c mein hon, toh c + 1 size ke array mein har value gino, phir order mein likh do. Total O(n + c) — c = O(n) ho toh linear.
/** O(n + c) for values in 0..c: count, then write each value out count times. */static void countingSort(int[] a, int c) { int[] count = new int[c + 1]; for (int x : a) count[x]++; int k = 0; for (int v = 0; v <= c; v++) { for (int t = 0; t < count[v]; t++) a[k++] = v; }}My notesMere notes
3.2Sorting in Java
Never hand-write a sort in a contest; the library version is correct and fast. Here’s how the book’s C++ maps to Java:
| C++ | Java |
|---|---|
sort(v.begin(), v.end()) on ints | Arrays.sort(int[]) (shuffle first, see below) |
sort on objects | Arrays.sort(T[]), Collections.sort(list), list.sort(cmp) |
sort(v.rbegin(), v.rend()) | Arrays.sort(Integer[], Collections.reverseOrder()) |
pair<int,int> order | int[][] + a comparator on [0] then [1] |
operator< in a struct | implements Comparable<T> |
| comparison function | Comparator.comparingInt(...).thenComparing(...) |
Contest mein kabhi khud ka sort mat likho — library wala sahi bhi hai aur fast bhi. Book ka C++ Java mein aise map hota hai:
| C++ | Java |
|---|---|
ints pe sort(v.begin(), v.end()) | Arrays.sort(int[]) (pehle shuffle — neeche dekho) |
objects pe sort | Arrays.sort(T[]), Collections.sort(list), list.sort(cmp) |
sort(v.rbegin(), v.rend()) | Arrays.sort(Integer[], Collections.reverseOrder()) |
pair<int,int> wala order | int[][] + [0] phir [1] pe comparator |
struct mein operator< | implements Comparable<T> |
| comparison function | Comparator.comparingInt(...).thenComparing(...) |
/** * Arrays.sort(int[]) is a quicksort. On older Java versions a crafted test can make it O(n²) * ("anti-quicksort" hacks), so shuffle first; it costs O(n) and removes the bad case. */static void safeSort(int[] a) { Random rnd = new Random(); for (int i = a.length - 1; i > 0; i--) { int j = rnd.nextInt(i + 1); int t = a[i]; a[i] = a[j]; a[j] = t; } Arrays.sort(a);}/** C++ sorts pair<int,int> by first, then second. In Java, say so with a comparator. */static void sortPairs(int[][] pairs) { Arrays.sort(pairs, (p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));}/** A point that knows its own order: by x, then by y (C++'s operator<). */static class Point implements Comparable<Point> { final int x, y; Point(int x, int y) { this.x = x; this.y = y; } @Override public int compareTo(Point o) { if (x != o.x) return Integer.compare(x, o.x); return Integer.compare(y, o.y); }}/** Strings by length, then alphabetically (the book's comp function). */static void byLengthThenAlpha(List<String> words) { words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));}My notesMere notes
3.3Binary search
In a sorted array you don’t need to scan everything. Two equivalent methods, both O(log n):
- Method 1 (halving): keep an active region [lo, hi] and check its middle. If the middle value is too big, go left; if it’s too small, go right.
- Method 2 (jumps): walk from the left with jump lengths n/2, n/4, …, 1, never stepping onto a value larger than x.
Sorted array mein sab kuch scan karne ki zaroorat nahi. Do barabar tareeke, dono O(log n):
- Method 1 (halving): ek active region [lo, hi] rakho, beech wala dekho. Woh bada hai toh left jao, chhota hai toh right.
- Method 2 (jumps): left se n/2, n/4, …, 1 lambi jumps se chalo, kabhi x se badi value pe mat utro.
/** Index of x in sorted a, or -1. Keeps an active region [lo, hi] and halves it. */static int find(int[] a, int x) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int k = (lo + hi) >>> 1; if (a[k] == x) return k; if (a[k] > x) hi = k - 1; else lo = k + 1; } return -1;}/** Jump forward with lengths n/2, n/4, ..., 1, never past x. */static int findByJumps(int[] a, int x) { int n = a.length, k = 0; if (n == 0) return -1; for (int b = n / 2; b >= 1; b /= 2) { while (k + b < n && a[k + b] <= x) k += b; } return a[k] == x ? k : -1;}- left half / region
- current
- ruled out
- used in answer
x = 18 can only be in a[0..15] (16 elements).
/** Index of x in sorted a, or -1. Keeps an active region [lo, hi] and halves it. */static int find(int[] a, int x) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int k = (lo + hi) >>> 1; if (a[k] == x) return k; if (a[k] > x) hi = k - 1; else lo = k + 1; } return -1;}- lo
- 0
- hi
- 15
- x
- 18
Lower and upper bound
C++ has lower_bound (first element ≥ x) and upper_bound (first element > x). Their difference counts how often x occurs. Java’s Arrays.binarySearch is not the same: with duplicates it returns some matching index, and for a missing value it returns -(insertionPoint) - 1. Write your own bounds; they’re only six lines:
C++ mein lower_bound (pehla element ≥ x) aur upper_bound (pehla element > x) hain — dono ka difference batata hai x kitni baar hai. Java ka Arrays.binarySearch waisa nahi hai: duplicates mein koi bhi matching index deta hai, aur missing value pe -(insertionPoint) - 1. Apne bounds khud likho — sirf chhe lines:
/** First index with a[i] >= x (C++ lower_bound); a.length if none. */static int lowerBound(int[] a, int x) { int lo = 0, hi = a.length; // answer lies in [lo, hi] while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] >= x) hi = mid; else lo = mid + 1; } return lo;} /** First index with a[i] > x (C++ upper_bound). */static int upperBound(int[] a, int x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] > x) hi = mid; else lo = mid + 1; } return lo;}Binary search on the answer
Binary search works on any monotone yes/no question, not just arrays. If ok(x) is false for x < k and true for x ≥ k, jumping finds the smallest valid k with O(log z) calls to ok. “What is the minimum time to make t products?” is a typical example: ok(T) asks whether t products can be made in time T. The same idea finds the peak of a function that first increases and then decreases, as long as no two neighbouring values are equal.
Binary search kisi bhi monotone haan/naa sawaal pe chalta hai, sirf arrays pe nahi. Agar ok(x) x < k ke liye false aur x ≥ k ke liye true hai, toh jumps se sabse chhota valid k O(log z) baar ok call karke mil jaata hai. “t products banane ka minimum time kya hai?” iska typical example hai — ok(T) poochta hai: kya T time mein t products ban sakte hain? Yahi idea pehle badhne aur phir ghatne wale function ka peak bhi dhundh leta hai, bas padosi values barabar na hon.
/** Smallest k in [0, z] with ok(k) true, when ok is false…false true…true and ok(z) is true. */static int smallestTrue(IntPredicate ok, int z) { int x = -1; for (int b = z; b >= 1; b /= 2) { while (x + b <= z && !ok.test(x + b)) x += b; } return x + 1;}