Sorting arranges data in increasing or decreasing order. It is the most studied problem in computer science because so much else — binary search, deduplication, merging, finding medians, grouping — becomes easy once the data is sorted. These notes cover the library sorts you should actually call and the classic algorithms you must be able to write and analyse: bubble, selection, insertion, merge, quick and heap sort.
Comparison of sorting algorithms
The two properties interviewers ask about after time complexity are stability (equal elements keep their original relative order) and whether the sort is in-place (needs only O(1) — or O(log n) stack — extra memory).
| Algorithm | Best | Average | Worst | Extra space | Stable | In-place | Notes |
|---|---|---|---|---|---|---|---|
| Bubble sort | O(n)* | O(n²) | O(n²) | O(1) | yes | yes | *with the swapped flag; academic only |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | no | yes | fewest writes: at most n − 1 swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | yes | yes | best for small or nearly sorted input; used inside Timsort / introsort |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes | no | linked lists and external sorting; guaranteed n log n |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) stack | no | yes | fastest in practice: cache-friendly, low constants |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | no | yes | guaranteed n log n in place; poor cache behaviour |
| Timsort (library) | O(n) | O(n log n) | O(n log n) | O(n) | yes | no | merge sort + insertion sort on natural runs; Python, Java objects, V8 |
Built-in sorting in each language
In real code you call the library sort. Know what it runs, whether it is stable, and how to pass a key or comparator.
| Language | Call | Algorithm | Stable | Custom order |
|---|---|---|---|---|
| Python | sorted(iterable, key=, reverse=) → new list · list.sort() in place | Timsort | yes | key= function (len, abs, lambda p: (p.x, p.y)) |
| C++ | std::sort(begin, end, cmp) | introsort (quick + heap + insertion) | no | comparator: greater<int>(), lambda |
| C++ | std::stable_sort(begin, end, cmp) | merge sort | yes | same comparator |
| Java | Arrays.sort(int[]) (primitives) | dual-pivot quicksort | n/a (primitives are indistinguishable) | — |
| Java | Arrays.sort(T[]), Collections.sort(list), list.sort(cmp) | Timsort | yes | Comparator.comparingInt(...), reverseOrder() |
| JavaScript | arr.sort(cmp) in place · arr.toSorted(cmp) copy | Timsort (V8) | yes (since ES2019) | (a, b) => a - b — required for numbers |
nums = [5, 10, 15, 1]
print("ascending:", *sorted(nums))
print("descending:", *sorted(nums, reverse=True))
words = ["Thrishank", "Nani", "Kuntimaddi"]
print("by length:", *sorted(words, key=len)) # key: sort by what len() returns#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {5, 10, 15, 1};
sort(nums.begin(), nums.end());
cout << "ascending:";
for (int x : nums) cout << " " << x;
cout << "\n";
sort(nums.begin(), nums.end(), greater<int>()); // comparator: descending
cout << "descending:";
for (int x : nums) cout << " " << x;
cout << "\n";
vector<string> words = {"Thrishank", "Nani", "Kuntimaddi"};
stable_sort(words.begin(), words.end(), // stable: equal lengths keep their order
[](const string& a, const string& b) { return a.size() < b.size(); });
cout << "by length:";
for (const string& w : words) cout << " " << w;
cout << "\n";
}import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
Integer[] nums = {5, 10, 15, 1}; // boxed: needed for a Comparator
Arrays.sort(nums);
System.out.println("ascending: " + join(nums));
Arrays.sort(nums, Collections.reverseOrder()); // comparator: descending
System.out.println("descending: " + join(nums));
String[] words = {"Thrishank", "Nani", "Kuntimaddi"};
Arrays.sort(words, Comparator.comparingInt(String::length)); // Timsort: stable
System.out.println("by length: " + join(words));
}
static String join(Object[] a) {
StringBuilder sb = new StringBuilder();
for (Object x : a) sb.append(sb.length() == 0 ? "" : " ").append(x);
return sb.toString();
}
}const nums = [5, 10, 15, 1];
console.log("ascending:", [...nums].sort((a, b) => a - b).join(" ")); // numeric comparator!
console.log("descending:", [...nums].sort((a, b) => b - a).join(" "));
const words = ["Thrishank", "Nani", "Kuntimaddi"];
console.log("by length:", words.toSorted((a, b) => a.length - b.length).join(" ")); // stableascending: 1 5 10 15
descending: 15 10 5 1
by length: Nani Thrishank Kuntimaddiconst arr = [10, 9, 1, 100];
console.log([...arr].sort().join(" ")); // "10" < "9" as strings
console.log([...arr].sort((a, b) => a - b).join(" "));1 10 100 9
1 9 10 100Python: sort() and sorted()
list.sort() | sorted(iterable) | |
|---|---|---|
| Works on | lists only | any iterable: list, tuple, string, set, dict (its keys), generator |
| Result | sorts in place, returns None | returns a new list; the input is untouched |
| Parameters | key=, reverse= | key=, reverse= — identical meaning |
| Algorithm | Timsort, stable, O(n log n) worst, O(n) on sorted input | same |
l1 = [5, 10, 15, 1]
l1.sort() # in place
print(l1) # [1, 5, 10, 15]
l2 = [5, 10, 15, 1]
l2.sort(reverse=True)
print(l2) # [15, 10, 5, 1]
l3 = ['Thrishank', 'Nani', 'Kuntimaddi']
l3.sort() # strings: dictionary order
print(l3) # ['Kuntimaddi', 'Nani', 'Thrishank']
l4 = ['Thrishank', 'Nani', 'Kuntimaddi']
l4.sort(key=len) # sort by the key's value: 4, 9, 10
print(l4) # ['Nani', 'Thrishank', 'Kuntimaddi']
l4.sort(key=len, reverse=True)
print(l4) # ['Kuntimaddi', 'Thrishank', 'Nani']
print([5, 1, 3].sort()) # None ← sort() returns None: a classic slipSorting objects. Either pass a key function that extracts the field to compare, or define __lt__ on the class so the objects compare themselves. A tuple key such as (p.x, p.y) sorts by x and breaks ties by y.
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, other): # "less than": lets sort() compare Points directly
if self.x == other.x:
return self.y < other.y # tie on x → compare y
return self.x < other.x
pts = [Point(10, 15), Point(1, 15), Point(3, 8), Point(1, 7)]
by_x = sorted(pts, key=lambda p: p.x) # key function: compare x only (stable → 1 15 before 1 7)
print("by x:", *(f"({p.x},{p.y})" for p in by_x))
pts.sort() # uses __lt__: x, then y
print("by x then y:", *(f"({p.x},{p.y})" for p in pts))
pts.sort(key=lambda p: (p.y, p.x)) # tuple key: y, then x
print("by y then x:", *(f"({p.x},{p.y})" for p in pts))by x: (1,15) (1,7) (3,8) (10,15)
by x then y: (1,7) (1,15) (3,8) (10,15)
by y then x: (1,7) (3,8) (1,15) (10,15)sorted() on other iterables — the result is always a list, even for a tuple, string or set. A dict sorts by its keys.
l = [30, 8, 23, 76, 12, 1, 12]
print(sorted(l)) # [1, 8, 12, 12, 23, 30, 76]
print(l) # [30, 8, 23, 76, 12, 1, 12] ← untouched
l = [10, -15, -2, 1]
print(sorted(l, key=abs)) # [1, -2, 10, -15]
print(sorted(l, key=abs, reverse=True)) # [-15, 10, -2, 1]
print(sorted(l)) # [-15, -2, 1, 10]
print(sorted((10, 12, 5, 1))) # [1, 5, 10, 12]
print(sorted({'Thrishank', 'Nani', 'Kuntimaddi'})) # ['Kuntimaddi', 'Nani', 'Thrishank']
print(sorted('gfg')) # ['f', 'g', 'g']
print(sorted({10: 'a', 12: 'b', 5: 'c'})) # [5, 10, 12] ← keys only
print(sorted([(10, 15), (12, 15), (3, 8)])) # [(3, 8), (10, 15), (12, 15)]Stability
input (name, marks): (Anil, 50) (Ayan, 80) (Pyush, 50) (Ramesh, 80)
sort by marks, stable: (Anil, 50) (Pyush, 50) (Ayan, 80) (Ramesh, 80)
^ Anil still before Pyush, Ayan still before Ramesh
a possible unstable result: (Pyush, 50) (Anil, 50) (Ayan, 80) (Ramesh, 80)
^ the two 50s swapped — equal keys, order lostWhy it matters: stability lets you sort by several fields in passes. Sort by the secondary key first, then stably by the primary key — rows with the same primary key stay in secondary order. Spreadsheets, SQL ORDER BY a, b and "sort by marks, then alphabetically" all rely on this. It is also what makes sort by marks leave an already alphabetical list alphabetical within each group.
students = [("Ramesh", 80), ("Anil", 50), ("Pyush", 50), ("Ayan", 80)]
show = lambda rows: ", ".join(f"{name} {marks}" for name, marks in rows)
print("input:", show(students))
print("by marks only:", show(sorted(students, key=lambda s: s[1]))) # ties keep input order
by_name = sorted(students) # pass 1: secondary key
by_both = sorted(by_name, key=lambda s: s[1]) # pass 2: primary key, stable
print("by name, then by marks:", show(by_both))#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using Student = pair<string, int>;
void show(const char* label, const vector<Student>& rows) {
cout << label;
for (size_t i = 0; i < rows.size(); i++)
cout << (i ? ", " : " ") << rows[i].first << " " << rows[i].second;
cout << "\n";
}
int main() {
vector<Student> students = {{"Ramesh", 80}, {"Anil", 50}, {"Pyush", 50}, {"Ayan", 80}};
auto byMarks = [](const Student& a, const Student& b) { return a.second < b.second; };
show("input:", students);
vector<Student> v = students;
stable_sort(v.begin(), v.end(), byMarks); // std::sort would NOT guarantee the tie order
show("by marks only:", v);
v = students;
sort(v.begin(), v.end()); // pass 1: by name (pairs compare by first)
stable_sort(v.begin(), v.end(), byMarks); // pass 2: by marks, stable
show("by name, then by marks:", v);
}import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main {
record Student(String name, int marks) {}
static String show(List<Student> rows) {
StringBuilder sb = new StringBuilder();
for (Student s : rows) sb.append(sb.length() == 0 ? "" : ", ").append(s.name()).append(' ').append(s.marks());
return sb.toString();
}
public static void main(String[] args) {
List<Student> students = List.of(new Student("Ramesh", 80), new Student("Anil", 50),
new Student("Pyush", 50), new Student("Ayan", 80));
System.out.println("input: " + show(students));
List<Student> v = new ArrayList<>(students);
v.sort(Comparator.comparingInt(Student::marks)); // List.sort is Timsort: stable
System.out.println("by marks only: " + show(v));
v = new ArrayList<>(students);
v.sort(Comparator.comparing(Student::name)); // pass 1: by name
v.sort(Comparator.comparingInt(Student::marks)); // pass 2: by marks, stable
System.out.println("by name, then by marks: " + show(v));
}
}const students = [["Ramesh", 80], ["Anil", 50], ["Pyush", 50], ["Ayan", 80]];
const show = rows => rows.map(([name, marks]) => `${name} ${marks}`).join(", ");
console.log("input:", show(students));
console.log("by marks only:", show(students.toSorted((a, b) => a[1] - b[1]))); // stable since ES2019
const byName = students.toSorted((a, b) => a[0].localeCompare(b[0])); // pass 1: by name
const byBoth = byName.toSorted((a, b) => a[1] - b[1]); // pass 2: by marks, stable
console.log("by name, then by marks:", show(byBoth));input: Ramesh 80, Anil 50, Pyush 50, Ayan 80
by marks only: Anil 50, Pyush 50, Ramesh 80, Ayan 80
by name, then by marks: Anil 50, Pyush 50, Ayan 80, Ramesh 80| Stable | Not stable | Why |
|---|---|---|
| Bubble sort | Selection sort | selection swaps the minimum over elements it has not compared with — a long-distance swap can jump one equal element over another |
| Insertion sort | Quick sort | partition swaps elements across the whole range |
| Merge sort | Heap sort | the heap's swaps with the last leaf reorder equal keys |
| Timsort, counting sort | std::sort, Arrays.sort(int[]) | introsort / quicksort based |
Bubble sort
pass 1 on [5, 1, 4, 2]:
(5 1) 4 2 → swap → 1 5 4 2
1 (5 4) 2 → swap → 1 4 5 2
1 4 (5 2) → swap → 1 4 2 5 5 is now final
pass 2 on the first 3:
(1 4) 2 → ok
1 (4 2) → swap → 1 2 4 5 4 is now final
pass 3: (1 2) ok → no swap in the whole pass → sorteddef bubble_sort(arr):
n = len(arr)
passes = 0
for i in range(n - 1):
swapped = False
passes += 1
for j in range(n - i - 1): # last i elements are already in place
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # a clean pass: already sorted
break
return passes
for arr in ([10, 12, 5, 1, 10, 4, 56, 100], [1, 2, 3, 4, 5]):
passes = bubble_sort(arr)
print("sorted:", *arr)
print("passes:", passes)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int bubbleSort(vector<int>& arr) {
int n = arr.size(), passes = 0;
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
passes++;
for (int j = 0; j < n - i - 1; j++) { // last i elements are already in place
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // a clean pass: already sorted
}
return passes;
}
int main() {
vector<vector<int>> tests = {{10, 12, 5, 1, 10, 4, 56, 100}, {1, 2, 3, 4, 5}};
for (auto& arr : tests) {
int passes = bubbleSort(arr);
cout << "sorted:";
for (int x : arr) cout << " " << x;
cout << "\npasses: " << passes << "\n";
}
}public class Main {
static int bubbleSort(int[] arr) {
int n = arr.length, passes = 0;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
passes++;
for (int j = 0; j < n - i - 1; j++) { // last i elements are already in place
if (arr[j] > arr[j + 1]) {
int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break; // a clean pass: already sorted
}
return passes;
}
public static void main(String[] args) {
int[][] tests = {{10, 12, 5, 1, 10, 4, 56, 100}, {1, 2, 3, 4, 5}};
for (int[] arr : tests) {
int passes = bubbleSort(arr);
StringBuilder sb = new StringBuilder("sorted:");
for (int x : arr) sb.append(' ').append(x);
System.out.println(sb);
System.out.println("passes: " + passes);
}
}
}function bubbleSort(arr) {
const n = arr.length;
let passes = 0;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
passes++;
for (let j = 0; j < n - i - 1; j++) { // last i elements are already in place
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break; // a clean pass: already sorted
}
return passes;
}
for (const arr of [[10, 12, 5, 1, 10, 4, 56, 100], [1, 2, 3, 4, 5]]) {
const passes = bubbleSort(arr);
console.log("sorted:", arr.join(" "));
console.log("passes:", passes);
}sorted: 1 4 5 10 10 12 56 100
passes: 5
sorted: 1 2 3 4 5
passes: 1Time O(n²) — O(n) best with the swapped flag · Space O(1)
Stable: only adjacent elements are swapped, and only when strictly greater — equal neighbours never cross.
In-place, trivially simple — which is why it appears in every textbook and almost no real program.
Without the
swappedflag it always runsn − 1full passes, even on sorted input.
Selection sort
def selection_sort(arr, trace=False):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n): # find the minimum of arr[i..n-1]
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] # one swap per pass
if trace:
print(f"pass {i + 1}: min {arr[i]} ->", *arr)
selection_sort([29, 10, 14, 37, 13], trace=True)
arr = [10, 12, 5, 1, 10, 4, 56, 100]
selection_sort(arr)
print("sorted:", *arr)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void show(const vector<int>& arr) {
for (int x : arr) cout << " " << x;
cout << "\n";
}
void selectionSort(vector<int>& arr, bool trace = false) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) // find the minimum of arr[i..n-1]
if (arr[j] < arr[minIndex]) minIndex = j;
swap(arr[i], arr[minIndex]); // one swap per pass
if (trace) { cout << "pass " << i + 1 << ": min " << arr[i] << " ->"; show(arr); }
}
}
int main() {
vector<int> small = {29, 10, 14, 37, 13};
selectionSort(small, true);
vector<int> arr = {10, 12, 5, 1, 10, 4, 56, 100};
selectionSort(arr);
cout << "sorted:";
show(arr);
}public class Main {
static String join(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int x : arr) sb.append(' ').append(x);
return sb.toString();
}
static void selectionSort(int[] arr, boolean trace) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) // find the minimum of arr[i..n-1]
if (arr[j] < arr[minIndex]) minIndex = j;
int t = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = t; // one swap per pass
if (trace) System.out.println("pass " + (i + 1) + ": min " + arr[i] + " ->" + join(arr));
}
}
public static void main(String[] args) {
selectionSort(new int[]{29, 10, 14, 37, 13}, true);
int[] arr = {10, 12, 5, 1, 10, 4, 56, 100};
selectionSort(arr, false);
System.out.println("sorted:" + join(arr));
}
}function selectionSort(arr, trace = false) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) // find the minimum of arr[i..n-1]
if (arr[j] < arr[minIndex]) minIndex = j;
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // one swap per pass
if (trace) console.log(`pass ${i + 1}: min ${arr[i]} ->`, arr.join(" "));
}
}
selectionSort([29, 10, 14, 37, 13], true);
const arr = [10, 12, 5, 1, 10, 4, 56, 100];
selectionSort(arr);
console.log("sorted:", arr.join(" "));pass 1: min 10 -> 10 29 14 37 13
pass 2: min 13 -> 10 13 14 37 29
pass 3: min 14 -> 10 13 14 37 29
pass 4: min 29 -> 10 13 14 29 37
sorted: 1 4 5 10 10 12 56 100Time Θ(n²) in every case · Space O(1)
Always
Θ(n²)comparisons — it cannot notice that the input is already sorted.Fewest memory writes of the simple sorts (at most
n − 1swaps), useful when writes are expensive (flash memory). Cycle sort is the optimum for writes.Not stable: in pass 1 on
[2a, 2b, 1]the1is swapped with2a, which lands after2b.In-place. Its idea — repeatedly extract the minimum — is the seed of heap sort, which extracts it in
O(log n)instead ofO(n).
Insertion sort
i = 2, x = 5: [10, 12 | 5, 1, 10, 4]
shift 12 → [10, _, 12] shift 10 → [_, 10, 12] place 5 → [5, 10, 12 | 1, 10, 4]def insertion_sort(arr, trace=False):
for i in range(1, len(arr)):
x = arr[i] # the element to insert
j = i - 1
while j >= 0 and arr[j] > x: # shift larger elements right ...
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = x # ... and drop x into the gap
if trace:
print(f"insert {x}:", *arr)
insertion_sort([10, 12, 5, 1, 10, 4], trace=True)
arr = [10, 12, 5, 1, 10, 4, 56, 100]
insertion_sort(arr)
print("sorted:", *arr)#include <iostream>
#include <vector>
using namespace std;
void show(const vector<int>& arr) {
for (int x : arr) cout << " " << x;
cout << "\n";
}
void insertionSort(vector<int>& arr, bool trace = false) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int x = arr[i]; // the element to insert
int j = i - 1;
while (j >= 0 && arr[j] > x) { // shift larger elements right ...
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = x; // ... and drop x into the gap
if (trace) { cout << "insert " << x << ":"; show(arr); }
}
}
int main() {
vector<int> small = {10, 12, 5, 1, 10, 4};
insertionSort(small, true);
vector<int> arr = {10, 12, 5, 1, 10, 4, 56, 100};
insertionSort(arr);
cout << "sorted:";
show(arr);
}public class Main {
static String join(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int x : arr) sb.append(' ').append(x);
return sb.toString();
}
static void insertionSort(int[] arr, boolean trace) {
for (int i = 1; i < arr.length; i++) {
int x = arr[i]; // the element to insert
int j = i - 1;
while (j >= 0 && arr[j] > x) { // shift larger elements right ...
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = x; // ... and drop x into the gap
if (trace) System.out.println("insert " + x + ":" + join(arr));
}
}
public static void main(String[] args) {
insertionSort(new int[]{10, 12, 5, 1, 10, 4}, true);
int[] arr = {10, 12, 5, 1, 10, 4, 56, 100};
insertionSort(arr, false);
System.out.println("sorted:" + join(arr));
}
}function insertionSort(arr, trace = false) {
for (let i = 1; i < arr.length; i++) {
const x = arr[i]; // the element to insert
let j = i - 1;
while (j >= 0 && arr[j] > x) { // shift larger elements right ...
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = x; // ... and drop x into the gap
if (trace) console.log(`insert ${x}:`, arr.join(" "));
}
}
insertionSort([10, 12, 5, 1, 10, 4], true);
const arr = [10, 12, 5, 1, 10, 4, 56, 100];
insertionSort(arr);
console.log("sorted:", arr.join(" "));insert 12: 10 12 5 1 10 4
insert 5: 5 10 12 1 10 4
insert 1: 1 5 10 12 10 4
insert 10: 1 5 10 10 12 4
insert 4: 1 4 5 10 10 12
sorted: 1 4 5 10 10 12 56 100Time O(n²) worst / average · O(n) best (sorted input) · Space O(1)
Stable (shifts only strictly greater elements) and in-place.
The practical choice for small arrays (≈ 16–32 elements) and nearly sorted data — Timsort and introsort both switch to insertion sort for short ranges.
O(n + d)wheredis the number of inversions: an array with few elements out of place sorts in almost linear time.
Merging two sorted arrays
Naive: concatenate and sort — O((m + n) log(m + n)). It ignores the fact that both inputs are already sorted.
def merge_naive(a, b):
res = a + b
res.sort() # throws away the order we already had
return res
print(*merge_naive([10, 15, 20], [5, 6, 6, 30]))5 6 6 10 15 20 30a = [10, 15, 20] b = [5, 6, 6, 30] res = []
i j
10 > 5 → take 5 res = [5] j → 6
10 > 6 → take 6 res = [5 6] j → 6
10 > 6 → take 6 res = [5 6 6] j → 30
10 < 30 → take 10 res = [5 6 6 10] i → 15
15 < 30 → take 15 res = [5 6 6 10 15] i → 20
20 < 30 → take 20 res = [5 6 6 10 15 20] a is exhausted
copy the rest of b res = [5 6 6 10 15 20 30]def merge(a, b):
res = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps the merge stable (a's element first on a tie)
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
res.extend(a[i:]) # at most one of these has anything left
res.extend(b[j:])
return res
print(*merge([10, 15, 20], [5, 6, 6, 30]))#include <iostream>
#include <vector>
using namespace std;
vector<int> merge(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int m = a.size(), n = b.size(), i = 0, j = 0;
while (i < m && j < n) {
if (a[i] <= b[j]) res.push_back(a[i++]); // <= keeps the merge stable
else res.push_back(b[j++]);
}
while (i < m) res.push_back(a[i++]); // at most one of these has anything left
while (j < n) res.push_back(b[j++]);
return res;
}
int main() {
vector<int> res = merge({10, 15, 20}, {5, 6, 6, 30});
for (size_t k = 0; k < res.size(); k++) cout << (k ? " " : "") << res[k];
cout << "\n";
}public class Main {
static int[] merge(int[] a, int[] b) {
int m = a.length, n = b.length, i = 0, j = 0, k = 0;
int[] res = new int[m + n];
while (i < m && j < n) {
if (a[i] <= b[j]) res[k++] = a[i++]; // <= keeps the merge stable
else res[k++] = b[j++];
}
while (i < m) res[k++] = a[i++]; // at most one of these has anything left
while (j < n) res[k++] = b[j++];
return res;
}
public static void main(String[] args) {
int[] res = merge(new int[]{10, 15, 20}, new int[]{5, 6, 6, 30});
StringBuilder sb = new StringBuilder();
for (int x : res) sb.append(sb.length() == 0 ? "" : " ").append(x);
System.out.println(sb);
}
}function merge(a, b) {
const res = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) res.push(a[i++]); // <= keeps the merge stable
else res.push(b[j++]);
}
while (i < a.length) res.push(a[i++]); // at most one of these has anything left
while (j < b.length) res.push(b[j++]);
return res;
}
console.log(merge([10, 15, 20], [5, 6, 6, 30]).join(" "));5 6 6 10 15 20 30Time O(m + n) · Space O(m + n) for the result
Merge subarray
Merge sort needs the same merge, but inside one array: the two sorted halves are a[low..mid] and a[mid+1..high], and the merged result must land back in a[low..high]. Copy the two halves into temporary arrays left and right, then merge them back starting at index low.
def merge(a, low, mid, high):
left = a[low:mid + 1] # copies: a[low..mid] and a[mid+1..high]
right = a[mid + 1:high + 1]
i = j = 0
k = low # write position in a
while i < len(left) and j < len(right):
if left[i] <= right[j]:
a[k] = left[i]
i += 1
else:
a[k] = right[j]
j += 1
k += 1
while i < len(left): # leftovers
a[k] = left[i]
i += 1
k += 1
while j < len(right):
a[k] = right[j]
j += 1
k += 1
a = [10, 15, 20, 11, 13]
merge(a, 0, 2, 4)
print(*a)#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& a, int low, int mid, int high) {
vector<int> left(a.begin() + low, a.begin() + mid + 1); // a[low..mid]
vector<int> right(a.begin() + mid + 1, a.begin() + high + 1); // a[mid+1..high]
int nl = left.size(), nr = right.size(), i = 0, j = 0, k = low; // k: write position in a
while (i < nl && j < nr) {
if (left[i] <= right[j]) a[k++] = left[i++];
else a[k++] = right[j++];
}
while (i < nl) a[k++] = left[i++]; // leftovers
while (j < nr) a[k++] = right[j++];
}
int main() {
vector<int> a = {10, 15, 20, 11, 13};
merge(a, 0, 2, 4);
for (size_t k = 0; k < a.size(); k++) cout << (k ? " " : "") << a[k];
cout << "\n";
}import java.util.Arrays;
public class Main {
static void merge(int[] a, int low, int mid, int high) {
int[] left = Arrays.copyOfRange(a, low, mid + 1); // a[low..mid]
int[] right = Arrays.copyOfRange(a, mid + 1, high + 1); // a[mid+1..high]
int i = 0, j = 0, k = low; // k: write position in a
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) a[k++] = left[i++];
else a[k++] = right[j++];
}
while (i < left.length) a[k++] = left[i++]; // leftovers
while (j < right.length) a[k++] = right[j++];
}
public static void main(String[] args) {
int[] a = {10, 15, 20, 11, 13};
merge(a, 0, 2, 4);
StringBuilder sb = new StringBuilder();
for (int x : a) sb.append(sb.length() == 0 ? "" : " ").append(x);
System.out.println(sb);
}
}function merge(a, low, mid, high) {
const left = a.slice(low, mid + 1); // a[low..mid]
const right = a.slice(mid + 1, high + 1); // a[mid+1..high]
let i = 0, j = 0, k = low; // k: write position in a
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) a[k++] = left[i++];
else a[k++] = right[j++];
}
while (i < left.length) a[k++] = left[i++]; // leftovers
while (j < right.length) a[k++] = right[j++];
}
const a = [10, 15, 20, 11, 13];
merge(a, 0, 2, 4);
console.log(a.join(" "));10 11 13 15 20Time O(high − low + 1) · Space O(high − low + 1) temporary copies
Merge sort
[38 27 43 3 9 82 10]
/ \ divide
[38 27 43 3] [9 82 10]
/ \ / \
[38 27] [43 3] [9 82] [10]
/ \ / \ / \
[38] [27] [43] [3] [9] [82]
\ / \ / \ /
[27 38] [3 43] [9 82] [10] merge
\ / \ /
[3 27 38 43] [9 10 82]
\ /
[3 9 10 27 38 43 82]def merge(a, low, mid, high):
left, right = a[low:mid + 1], a[mid + 1:high + 1]
i = j = 0
k = low
while i < len(left) and j < len(right):
if left[i] <= right[j]:
a[k] = left[i]; i += 1
else:
a[k] = right[j]; j += 1
k += 1
while i < len(left):
a[k] = left[i]; i += 1; k += 1
while j < len(right):
a[k] = right[j]; j += 1; k += 1
def merge_sort(a, low, high):
if low < high: # at least two elements
mid = low + (high - low) // 2
merge_sort(a, low, mid) # sort the left half
merge_sort(a, mid + 1, high) # sort the right half
merge(a, low, mid, high) # combine
for arr in ([38, 27, 43, 3, 9, 82, 10], [10, 15, 20, 11, 13]):
merge_sort(arr, 0, len(arr) - 1)
print(*arr)#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& a, int low, int mid, int high) {
vector<int> left(a.begin() + low, a.begin() + mid + 1);
vector<int> right(a.begin() + mid + 1, a.begin() + high + 1);
int nl = left.size(), nr = right.size(), i = 0, j = 0, k = low;
while (i < nl && j < nr) a[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < nl) a[k++] = left[i++];
while (j < nr) a[k++] = right[j++];
}
void mergeSort(vector<int>& a, int low, int high) {
if (low < high) { // at least two elements
int mid = low + (high - low) / 2;
mergeSort(a, low, mid); // sort the left half
mergeSort(a, mid + 1, high); // sort the right half
merge(a, low, mid, high); // combine
}
}
int main() {
vector<vector<int>> tests = {{38, 27, 43, 3, 9, 82, 10}, {10, 15, 20, 11, 13}};
for (auto& arr : tests) {
mergeSort(arr, 0, (int)arr.size() - 1);
for (size_t k = 0; k < arr.size(); k++) cout << (k ? " " : "") << arr[k];
cout << "\n";
}
}import java.util.Arrays;
public class Main {
static void merge(int[] a, int low, int mid, int high) {
int[] left = Arrays.copyOfRange(a, low, mid + 1);
int[] right = Arrays.copyOfRange(a, mid + 1, high + 1);
int i = 0, j = 0, k = low;
while (i < left.length && j < right.length) a[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < left.length) a[k++] = left[i++];
while (j < right.length) a[k++] = right[j++];
}
static void mergeSort(int[] a, int low, int high) {
if (low < high) { // at least two elements
int mid = low + (high - low) / 2;
mergeSort(a, low, mid); // sort the left half
mergeSort(a, mid + 1, high); // sort the right half
merge(a, low, mid, high); // combine
}
}
public static void main(String[] args) {
int[][] tests = {{38, 27, 43, 3, 9, 82, 10}, {10, 15, 20, 11, 13}};
for (int[] arr : tests) {
mergeSort(arr, 0, arr.length - 1);
StringBuilder sb = new StringBuilder();
for (int x : arr) sb.append(sb.length() == 0 ? "" : " ").append(x);
System.out.println(sb);
}
}
}function merge(a, low, mid, high) {
const left = a.slice(low, mid + 1), right = a.slice(mid + 1, high + 1);
let i = 0, j = 0, k = low;
while (i < left.length && j < right.length) a[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < left.length) a[k++] = left[i++];
while (j < right.length) a[k++] = right[j++];
}
function mergeSort(a, low, high) {
if (low < high) { // at least two elements
const mid = low + Math.floor((high - low) / 2);
mergeSort(a, low, mid); // sort the left half
mergeSort(a, mid + 1, high); // sort the right half
merge(a, low, mid, high); // combine
}
}
for (const arr of [[38, 27, 43, 3, 9, 82, 10], [10, 15, 20, 11, 13]]) {
mergeSort(arr, 0, arr.length - 1);
console.log(arr.join(" "));
}3 9 10 27 38 43 82
10 11 13 15 20Time Θ(n log n) in every case · Space O(n) temporary arrays + O(log n) stack
T(n) = 2 T(n / 2) + Θ(n) ⇒ T(n) = Θ(n log n)
Stable (the
<=in merge) and guaranteedΘ(n log n)— no bad inputs, unlike quick sort.Not in-place: the merge needs
O(n)temporary space. (In-place variants exist but are slow or complex.)Ideal for linked lists: splitting and merging lists needs no extra array, so it sorts a list in
O(1)auxiliary space — and it is the default list sort in many libraries.Used in external sorting (data larger than memory): sort chunks that fit in RAM, then merge the sorted chunks sequentially from disk.
Timsort is merge sort with insertion-sorted runs; it is what Python and Java's object sort run.
Union of two sorted arrays
The union is every distinct value present in either array, in sorted order. Naive: concatenate, sort, then print each element that differs from its predecessor — O((m + n) log(m + n)).
def union_naive(a, b):
c = sorted(a + b)
return [c[i] for i in range(len(c)) if i == 0 or c[i] != c[i - 1]] # skip repeats
print(*union_naive([3, 5, 8, 9, 10, 15], [2, 8, 9, 10, 15]))2 3 5 8 9 10 15def union(a, b):
res = []
i = j = 0
m, n = len(a), len(b)
while i < m and j < n:
if i > 0 and a[i] == a[i - 1]: # duplicate inside a: skip
i += 1
elif j > 0 and b[j] == b[j - 1]: # duplicate inside b: skip
j += 1
elif a[i] < b[j]:
res.append(a[i]); i += 1
elif a[i] > b[j]:
res.append(b[j]); j += 1
else: # equal: take once, advance both
res.append(a[i]); i += 1; j += 1
while i < m: # leftovers of a (still skipping duplicates)
if i == 0 or a[i] != a[i - 1]:
res.append(a[i])
i += 1
while j < n: # leftovers of b
if j == 0 or b[j] != b[j - 1]:
res.append(b[j])
j += 1
return res
print(*union([3, 5, 8, 9, 10, 15], [2, 8, 9, 10, 15]))
print(*union([1, 1, 3, 3, 5], [1, 2, 2, 3]))#include <iostream>
#include <vector>
using namespace std;
vector<int> unionOf(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int m = a.size(), n = b.size(), i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && a[i] == a[i - 1]) i++; // duplicate inside a: skip
else if (j > 0 && b[j] == b[j - 1]) j++; // duplicate inside b: skip
else if (a[i] < b[j]) res.push_back(a[i++]);
else if (a[i] > b[j]) res.push_back(b[j++]);
else { res.push_back(a[i]); i++; j++; } // equal: take once, advance both
}
for (; i < m; i++) if (i == 0 || a[i] != a[i - 1]) res.push_back(a[i]); // leftovers of a
for (; j < n; j++) if (j == 0 || b[j] != b[j - 1]) res.push_back(b[j]); // leftovers of b
return res;
}
void show(const vector<int>& v) {
for (size_t k = 0; k < v.size(); k++) cout << (k ? " " : "") << v[k];
cout << "\n";
}
int main() {
show(unionOf({3, 5, 8, 9, 10, 15}, {2, 8, 9, 10, 15}));
show(unionOf({1, 1, 3, 3, 5}, {1, 2, 2, 3}));
}import java.util.ArrayList;
import java.util.List;
public class Main {
static List<Integer> union(int[] a, int[] b) {
List<Integer> res = new ArrayList<>();
int m = a.length, n = b.length, i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && a[i] == a[i - 1]) i++; // duplicate inside a: skip
else if (j > 0 && b[j] == b[j - 1]) j++; // duplicate inside b: skip
else if (a[i] < b[j]) res.add(a[i++]);
else if (a[i] > b[j]) res.add(b[j++]);
else { res.add(a[i]); i++; j++; } // equal: take once, advance both
}
for (; i < m; i++) if (i == 0 || a[i] != a[i - 1]) res.add(a[i]); // leftovers of a
for (; j < n; j++) if (j == 0 || b[j] != b[j - 1]) res.add(b[j]); // leftovers of b
return res;
}
static void show(List<Integer> v) {
StringBuilder sb = new StringBuilder();
for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
System.out.println(sb);
}
public static void main(String[] args) {
show(union(new int[]{3, 5, 8, 9, 10, 15}, new int[]{2, 8, 9, 10, 15}));
show(union(new int[]{1, 1, 3, 3, 5}, new int[]{1, 2, 2, 3}));
}
}function union(a, b) {
const res = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (i > 0 && a[i] === a[i - 1]) i++; // duplicate inside a: skip
else if (j > 0 && b[j] === b[j - 1]) j++; // duplicate inside b: skip
else if (a[i] < b[j]) res.push(a[i++]);
else if (a[i] > b[j]) res.push(b[j++]);
else { res.push(a[i]); i++; j++; } // equal: take once, advance both
}
for (; i < a.length; i++) if (i === 0 || a[i] !== a[i - 1]) res.push(a[i]); // leftovers of a
for (; j < b.length; j++) if (j === 0 || b[j] !== b[j - 1]) res.push(b[j]); // leftovers of b
return res;
}
console.log(union([3, 5, 8, 9, 10, 15], [2, 8, 9, 10, 15]).join(" "));
console.log(union([1, 1, 3, 3, 5], [1, 2, 2, 3]).join(" "));2 3 5 8 9 10 15
1 2 3 5Time O(m + n) · Space O(m + n) for the result
Intersection of two sorted arrays
The intersection is every distinct value present in both arrays. Naive: for each element of a (skipping repeats), scan b for it — O(m · n).
def intersection_naive(a, b):
res = []
for i in range(len(a)):
if i > 0 and a[i] == a[i - 1]:
continue # already handled this value
for x in b: # linear scan of b
if x == a[i]:
res.append(x)
break
return res
print(*intersection_naive([3, 5, 10, 10, 10, 10, 15, 15, 20], [5, 10, 10, 15, 30]))5 10 15def intersection(a, b):
res = []
i = j = 0
while i < len(a) and j < len(b):
if i > 0 and a[i] == a[i - 1]: # duplicate inside a: skip
i += 1
elif a[i] < b[j]: # a[i] is too small to be in b from here on
i += 1
elif a[i] > b[j]: # b[j] is too small
j += 1
else: # common value
res.append(a[i]); i += 1; j += 1
return res
print(*intersection([3, 5, 10, 10, 10, 10, 15, 15, 20], [5, 10, 10, 15, 30]))
print(*intersection([1, 2, 2, 3, 3, 3], [2, 2, 3, 4]))#include <iostream>
#include <vector>
using namespace std;
vector<int> intersection(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int m = a.size(), n = b.size(), i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && a[i] == a[i - 1]) i++; // duplicate inside a: skip
else if (a[i] < b[j]) i++; // a[i] is too small to be in b from here on
else if (a[i] > b[j]) j++; // b[j] is too small
else { res.push_back(a[i]); i++; j++; } // common value
}
return res;
}
void show(const vector<int>& v) {
for (size_t k = 0; k < v.size(); k++) cout << (k ? " " : "") << v[k];
cout << "\n";
}
int main() {
show(intersection({3, 5, 10, 10, 10, 10, 15, 15, 20}, {5, 10, 10, 15, 30}));
show(intersection({1, 2, 2, 3, 3, 3}, {2, 2, 3, 4}));
}import java.util.ArrayList;
import java.util.List;
public class Main {
static List<Integer> intersection(int[] a, int[] b) {
List<Integer> res = new ArrayList<>();
int m = a.length, n = b.length, i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && a[i] == a[i - 1]) i++; // duplicate inside a: skip
else if (a[i] < b[j]) i++; // a[i] is too small to be in b from here on
else if (a[i] > b[j]) j++; // b[j] is too small
else { res.add(a[i]); i++; j++; } // common value
}
return res;
}
static void show(List<Integer> v) {
StringBuilder sb = new StringBuilder();
for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
System.out.println(sb);
}
public static void main(String[] args) {
show(intersection(new int[]{3, 5, 10, 10, 10, 10, 15, 15, 20}, new int[]{5, 10, 10, 15, 30}));
show(intersection(new int[]{1, 2, 2, 3, 3, 3}, new int[]{2, 2, 3, 4}));
}
}function intersection(a, b) {
const res = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (i > 0 && a[i] === a[i - 1]) i++; // duplicate inside a: skip
else if (a[i] < b[j]) i++; // a[i] is too small to be in b from here on
else if (a[i] > b[j]) j++; // b[j] is too small
else { res.push(a[i]); i++; j++; } // common value
}
return res;
}
console.log(intersection([3, 5, 10, 10, 10, 10, 15, 15, 20], [5, 10, 10, 15, 30]).join(" "));
console.log(intersection([1, 2, 2, 3, 3, 3], [2, 2, 3, 4]).join(" "));5 10 15
2 3Time O(m + n) · Space O(min(m, n)) for the result
Count inversions
Naive: check every pair — O(n²).
def count_inversions_naive(arr):
n = len(arr)
count = 0
for i in range(n - 1):
for j in range(i + 1, n):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([2, 4, 1, 3, 5]), count_inversions_naive([2, 4, 1, 3, 5, 2]))3 6merge left = [2 4] right = [1 3 5]
take 1 from right → 1 < every remaining left element (2, 4) → +2 inversions
take 2 from left
take 3 from right → 3 < remaining left (4) → +1 inversion
take 4, 5 total: 3def count_merge(arr, low, mid, high):
left, right = arr[low:mid + 1], arr[mid + 1:high + 1]
count = 0
i = j = 0
k = low
while i < len(left) and j < len(right):
if left[i] <= right[j]:
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
count += len(left) - i # right[j] is smaller than all remaining left elements
k += 1
while i < len(left):
arr[k] = left[i]; i += 1; k += 1
while j < len(right):
arr[k] = right[j]; j += 1; k += 1
return count
def count_inversions(arr, low, high):
count = 0
if low < high:
mid = low + (high - low) // 2
count += count_inversions(arr, low, mid) # both in the left half
count += count_inversions(arr, mid + 1, high) # both in the right half
count += count_merge(arr, low, mid, high) # one in each half
return count
for arr in ([2, 4, 1, 3, 5], [2, 4, 1, 3, 5, 2], [5, 4, 3, 2, 1], [1, 2, 3, 4, 5]):
label = "[" + " ".join(map(str, arr)) + "]"
print(f"{label}:", count_inversions(arr, 0, len(arr) - 1)) # note: arr ends up sorted#include <iostream>
#include <vector>
using namespace std;
long long countMerge(vector<int>& arr, int low, int mid, int high) {
vector<int> left(arr.begin() + low, arr.begin() + mid + 1);
vector<int> right(arr.begin() + mid + 1, arr.begin() + high + 1);
int nl = left.size(), nr = right.size(), i = 0, j = 0, k = low;
long long count = 0;
while (i < nl && j < nr) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else { arr[k++] = right[j++]; count += nl - i; } // right[j] < all remaining left elements
}
while (i < nl) arr[k++] = left[i++];
while (j < nr) arr[k++] = right[j++];
return count;
}
long long countInversions(vector<int>& arr, int low, int high) {
long long count = 0;
if (low < high) {
int mid = low + (high - low) / 2;
count += countInversions(arr, low, mid); // both in the left half
count += countInversions(arr, mid + 1, high); // both in the right half
count += countMerge(arr, low, mid, high); // one in each half
}
return count;
}
int main() {
vector<vector<int>> tests = {{2, 4, 1, 3, 5}, {2, 4, 1, 3, 5, 2}, {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}};
for (auto& arr : tests) {
cout << "[";
for (size_t k = 0; k < arr.size(); k++) cout << (k ? " " : "") << arr[k];
cout << "]: " << countInversions(arr, 0, (int)arr.size() - 1) << "\n"; // arr ends up sorted
}
}import java.util.Arrays;
public class Main {
static long countMerge(int[] arr, int low, int mid, int high) {
int[] left = Arrays.copyOfRange(arr, low, mid + 1);
int[] right = Arrays.copyOfRange(arr, mid + 1, high + 1);
int i = 0, j = 0, k = low;
long count = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else { arr[k++] = right[j++]; count += left.length - i; } // right[j] < all remaining left
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
return count;
}
static long countInversions(int[] arr, int low, int high) {
long count = 0;
if (low < high) {
int mid = low + (high - low) / 2;
count += countInversions(arr, low, mid); // both in the left half
count += countInversions(arr, mid + 1, high); // both in the right half
count += countMerge(arr, low, mid, high); // one in each half
}
return count;
}
public static void main(String[] args) {
int[][] tests = {{2, 4, 1, 3, 5}, {2, 4, 1, 3, 5, 2}, {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}};
for (int[] arr : tests) {
StringBuilder sb = new StringBuilder("[");
for (int k = 0; k < arr.length; k++) sb.append(k > 0 ? " " : "").append(arr[k]);
System.out.println(sb + "]: " + countInversions(arr, 0, arr.length - 1)); // arr ends up sorted
}
}
}function countMerge(arr, low, mid, high) {
const left = arr.slice(low, mid + 1), right = arr.slice(mid + 1, high + 1);
let i = 0, j = 0, k = low, count = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else { arr[k++] = right[j++]; count += left.length - i; } // right[j] < all remaining left
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
return count;
}
function countInversions(arr, low, high) {
let count = 0;
if (low < high) {
const mid = low + Math.floor((high - low) / 2);
count += countInversions(arr, low, mid); // both in the left half
count += countInversions(arr, mid + 1, high); // both in the right half
count += countMerge(arr, low, mid, high); // one in each half
}
return count;
}
for (const arr of [[2, 4, 1, 3, 5], [2, 4, 1, 3, 5, 2], [5, 4, 3, 2, 1], [1, 2, 3, 4, 5]]) {
const label = "[" + arr.join(" ") + "]";
console.log(`${label}:`, countInversions(arr, 0, arr.length - 1)); // arr ends up sorted
}[2 4 1 3 5]: 3
[2 4 1 3 5 2]: 6
[5 4 3 2 1]: 10
[1 2 3 4 5]: 0Time O(n log n) · Space O(n)
Partition around a pivot
Naive, stable partition: move the pivot to the end, copy the ≤ pivot elements and then the > pivot elements into a temporary array, copy back — O(n) time but O(n) extra space.
def partition_naive(arr, p):
n = len(arr)
arr[p], arr[n - 1] = arr[n - 1], arr[p] # pivot goes to the end
pivot = arr[n - 1]
temp = [x for x in arr if x <= pivot] # smaller-or-equal first (includes the pivot) ...
temp += [x for x in arr if x > pivot] # ... then the larger ones; order inside each part kept
arr[:] = temp
return len([x for x in arr if x <= pivot]) - 1 # index of the pivot
arr = [3, 8, 6, 12, 10, 7]
print("pivot index:", partition_naive(arr, 5))
print(*arr)pivot index: 2
3 6 7 8 12 10The two in-place schemes below do it in O(1) extra space. Both are unstable.
Lomuto partition
pivot = 70 zone of <= pivot | zone of > pivot | unscanned
start i=-1 [10 80 30 90 40 50 | 70]
j=0 10<=70 i=0 [10 | 80 30 90 40 50 | 70]
j=1 80 > 70 [10 | 80 30 90 40 50 | 70]
j=2 30<=70 i=1 [10 30 | 80 90 40 50 | 70] swap arr[1], arr[2]
j=3 90 > 70 [10 30 | 80 90 40 50 | 70]
j=4 40<=70 i=2 [10 30 40 | 90 80 50 | 70] swap arr[2], arr[4]
j=5 50<=70 i=3 [10 30 40 50 | 80 90 | 70] swap arr[3], arr[5]
end: swap pivot into i+1 = 4 → [10 30 40 50 | 70 | 90 80]def lomuto_partition(arr, low, high):
pivot = arr[high] # last element is the pivot
i = low - 1 # end of the "<= pivot" zone
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # pull arr[j] into the zone
arr[i + 1], arr[high] = arr[high], arr[i + 1] # pivot goes between the zones
return i + 1
arr = [10, 80, 30, 90, 40, 50, 70]
print("before:", *arr)
print("pivot index:", lomuto_partition(arr, 0, len(arr) - 1))
print("after:", *arr)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int lomutoPartition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // last element is the pivot
int i = low - 1; // end of the "<= pivot" zone
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) swap(arr[++i], arr[j]); // pull arr[j] into the zone
}
swap(arr[i + 1], arr[high]); // pivot goes between the zones
return i + 1;
}
void show(const char* label, const vector<int>& v) {
cout << label;
for (int x : v) cout << " " << x;
cout << "\n";
}
int main() {
vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
show("before:", arr);
cout << "pivot index: " << lomutoPartition(arr, 0, (int)arr.size() - 1) << "\n";
show("after:", arr);
}public class Main {
static int lomutoPartition(int[] arr, int low, int high) {
int pivot = arr[high]; // last element is the pivot
int i = low - 1; // end of the "<= pivot" zone
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int t = arr[i]; arr[i] = arr[j]; arr[j] = t; // pull arr[j] into the zone
}
}
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t; // pivot between the zones
return i + 1;
}
static String join(int[] a) {
StringBuilder sb = new StringBuilder();
for (int x : a) sb.append(' ').append(x);
return sb.toString();
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70};
System.out.println("before:" + join(arr));
System.out.println("pivot index: " + lomutoPartition(arr, 0, arr.length - 1));
System.out.println("after:" + join(arr));
}
}function lomutoPartition(arr, low, high) {
const pivot = arr[high]; // last element is the pivot
let i = low - 1; // end of the "<= pivot" zone
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // pull arr[j] into the zone
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // pivot goes between the zones
return i + 1;
}
const arr = [10, 80, 30, 90, 40, 50, 70];
console.log("before:", arr.join(" "));
console.log("pivot index:", lomutoPartition(arr, 0, arr.length - 1));
console.log("after:", arr.join(" "));before: 10 80 30 90 40 50 70
pivot index: 4
after: 10 30 40 50 70 90 80Time O(n) · Space O(1)
Hoare partition
def hoare_partition(arr, low, high):
pivot = arr[low] # first element is the pivot
i, j = low - 1, high + 1
while True:
i += 1
while arr[i] < pivot: # stop at something >= pivot
i += 1
j -= 1
while arr[j] > pivot: # stop at something <= pivot
j -= 1
if i >= j: # crossed: [low..j] <= pivot <= [j+1..high]
return j
arr[i], arr[j] = arr[j], arr[i]
arr = [10, 80, 30, 90, 40, 50, 70, 100, 120, 10, 5]
print("before:", *arr)
print("returned:", hoare_partition(arr, 0, len(arr) - 1))
print("after:", *arr)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int hoarePartition(vector<int>& arr, int low, int high) {
int pivot = arr[low]; // first element is the pivot
int i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // stop at something >= pivot
do { j--; } while (arr[j] > pivot); // stop at something <= pivot
if (i >= j) return j; // crossed: [low..j] <= pivot <= [j+1..high]
swap(arr[i], arr[j]);
}
}
void show(const char* label, const vector<int>& v) {
cout << label;
for (int x : v) cout << " " << x;
cout << "\n";
}
int main() {
vector<int> arr = {10, 80, 30, 90, 40, 50, 70, 100, 120, 10, 5};
show("before:", arr);
cout << "returned: " << hoarePartition(arr, 0, (int)arr.size() - 1) << "\n";
show("after:", arr);
}public class Main {
static int hoarePartition(int[] arr, int low, int high) {
int pivot = arr[low]; // first element is the pivot
int i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // stop at something >= pivot
do { j--; } while (arr[j] > pivot); // stop at something <= pivot
if (i >= j) return j; // crossed: [low..j] <= pivot <= [j+1..high]
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
static String join(int[] a) {
StringBuilder sb = new StringBuilder();
for (int x : a) sb.append(' ').append(x);
return sb.toString();
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70, 100, 120, 10, 5};
System.out.println("before:" + join(arr));
System.out.println("returned: " + hoarePartition(arr, 0, arr.length - 1));
System.out.println("after:" + join(arr));
}
}function hoarePartition(arr, low, high) {
const pivot = arr[low]; // first element is the pivot
let i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // stop at something >= pivot
do { j--; } while (arr[j] > pivot); // stop at something <= pivot
if (i >= j) return j; // crossed: [low..j] <= pivot <= [j+1..high]
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
const arr = [10, 80, 30, 90, 40, 50, 70, 100, 120, 10, 5];
console.log("before:", arr.join(" "));
console.log("returned:", hoarePartition(arr, 0, arr.length - 1));
console.log("after:", arr.join(" "));before: 10 80 30 90 40 50 70 100 120 10 5
returned: 1
after: 5 10 30 90 40 50 70 100 120 80 10Time O(n) · Space O(1)
| Lomuto | Hoare | |
|---|---|---|
| Pivot | last element arr[high] | first element arr[low] |
| Returns | the pivot's final index p | a boundary j; the pivot is somewhere in [low..j] |
| Quick sort recursion | [low..p−1] and [p+1..high] | [low..j] and [j+1..high] |
| Swaps | about n/2 on average | about n/6 — roughly three times fewer |
| All-equal input | degenerates: every element goes left → O(n²) | splits in the middle → stays O(n log n) |
| Simplicity | easier to get right | the stop conditions and the i >= j test are easy to get wrong |
Quick sort
[3 5 6 7 1 2 4] pivot 4 (Lomuto, last)
↓ partition
[3 1 2] 4 [5 6 7] 4 is final
↓ ↓
[1] 2 [3] [5 6] 7 2 and 7 are final
↓
[5] 6 6 is final
result: 1 2 3 4 5 6 7def lomuto_partition(arr, low, high):
pivot, i = arr[high], low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def hoare_partition(arr, low, high):
pivot, i, j = arr[low], low - 1, high + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_lomuto(arr, low, high):
if low < high:
p = lomuto_partition(arr, low, high)
quick_sort_lomuto(arr, low, p - 1) # pivot at p is final: skip it
quick_sort_lomuto(arr, p + 1, high)
def quick_sort_hoare(arr, low, high):
if low < high:
p = hoare_partition(arr, low, high)
quick_sort_hoare(arr, low, p) # p is a boundary, not the pivot: include it
quick_sort_hoare(arr, p + 1, high)
for arr in ([10, 80, 30, 90, 40, 50, 70], [3, 5, 6, 7, 1, 2, 4]):
a, b = arr[:], arr[:]
quick_sort_lomuto(a, 0, len(a) - 1)
quick_sort_hoare(b, 0, len(b) - 1)
print("lomuto:", *a)
print("hoare:", *b)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int lomutoPartition(vector<int>& arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] <= pivot) swap(arr[++i], arr[j]);
swap(arr[i + 1], arr[high]);
return i + 1;
}
int hoarePartition(vector<int>& arr, int low, int high) {
int pivot = arr[low], i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
swap(arr[i], arr[j]);
}
}
void quickSortLomuto(vector<int>& arr, int low, int high) {
if (low < high) {
int p = lomutoPartition(arr, low, high);
quickSortLomuto(arr, low, p - 1); // pivot at p is final: skip it
quickSortLomuto(arr, p + 1, high);
}
}
void quickSortHoare(vector<int>& arr, int low, int high) {
if (low < high) {
int p = hoarePartition(arr, low, high);
quickSortHoare(arr, low, p); // p is a boundary, not the pivot: include it
quickSortHoare(arr, p + 1, high);
}
}
void show(const char* label, const vector<int>& v) {
cout << label;
for (int x : v) cout << " " << x;
cout << "\n";
}
int main() {
vector<vector<int>> tests = {{10, 80, 30, 90, 40, 50, 70}, {3, 5, 6, 7, 1, 2, 4}};
for (const auto& arr : tests) {
vector<int> a = arr, b = arr;
quickSortLomuto(a, 0, (int)a.size() - 1);
quickSortHoare(b, 0, (int)b.size() - 1);
show("lomuto:", a);
show("hoare:", b);
}
}public class Main {
static int lomutoPartition(int[] arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] <= pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
return i + 1;
}
static int hoarePartition(int[] arr, int low, int high) {
int pivot = arr[low], i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
static void quickSortLomuto(int[] arr, int low, int high) {
if (low < high) {
int p = lomutoPartition(arr, low, high);
quickSortLomuto(arr, low, p - 1); // pivot at p is final: skip it
quickSortLomuto(arr, p + 1, high);
}
}
static void quickSortHoare(int[] arr, int low, int high) {
if (low < high) {
int p = hoarePartition(arr, low, high);
quickSortHoare(arr, low, p); // p is a boundary, not the pivot: include it
quickSortHoare(arr, p + 1, high);
}
}
static String join(int[] a) {
StringBuilder sb = new StringBuilder();
for (int x : a) sb.append(' ').append(x);
return sb.toString();
}
public static void main(String[] args) {
int[][] tests = {{10, 80, 30, 90, 40, 50, 70}, {3, 5, 6, 7, 1, 2, 4}};
for (int[] arr : tests) {
int[] a = arr.clone(), b = arr.clone();
quickSortLomuto(a, 0, a.length - 1);
quickSortHoare(b, 0, b.length - 1);
System.out.println("lomuto:" + join(a));
System.out.println("hoare:" + join(b));
}
}
}function lomutoPartition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++)
if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function hoarePartition(arr, low, high) {
const pivot = arr[low];
let i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
function quickSortLomuto(arr, low, high) {
if (low < high) {
const p = lomutoPartition(arr, low, high);
quickSortLomuto(arr, low, p - 1); // pivot at p is final: skip it
quickSortLomuto(arr, p + 1, high);
}
}
function quickSortHoare(arr, low, high) {
if (low < high) {
const p = hoarePartition(arr, low, high);
quickSortHoare(arr, low, p); // p is a boundary, not the pivot: include it
quickSortHoare(arr, p + 1, high);
}
}
for (const arr of [[10, 80, 30, 90, 40, 50, 70], [3, 5, 6, 7, 1, 2, 4]]) {
const a = [...arr], b = [...arr];
quickSortLomuto(a, 0, a.length - 1);
quickSortHoare(b, 0, b.length - 1);
console.log("lomuto:", a.join(" "));
console.log("hoare:", b.join(" "));
}lomuto: 10 30 40 50 70 80 90
hoare: 10 30 40 50 70 80 90
lomuto: 1 2 3 4 5 6 7
hoare: 1 2 3 4 5 6 7Time O(n log n) average · O(n²) worst · Space O(log n) stack on average
Analysis of quick sort
| Case | When | Recurrence | Time |
|---|---|---|---|
| Best | every partition splits in half | T(n) = 2T(n/2) + Θ(n) | Θ(n log n) |
| Average | random pivots / random input | T(n) = T(n/4) + T(3n/4) + Θ(n) (a typical uneven split) | Θ(n log n) — about 1.39 n log2 n comparisons |
| Worst | the pivot is always the min or max — sorted input with first/last pivot, or all equal values with Lomuto | T(n) = T(n − 1) + Θ(n) | Θ(n²) |
| Space | recursion depth | O(log n) average; O(n) in the worst case unless the smaller side is recursed first |
Despite the O(n²) worst case, quick sort is usually the fastest comparison sort in practice:
Heap sort
array [12 10 7 5 1 3 4] as a max-heap: children of i are 2i+1 and 2i+2
12 (0)
/ \
10 (1) 7 (2)
/ \ / \
5 (3) 1 (4) 3 (5) 4 (6)
swap root 12 with last (4) → [4 10 7 5 1 3 | 12] heapify 4 down over the first 6heapify(i)
Compare node
iwith its children; swap with the larger child if it is bigger, and continue down.O(log n).build heap
Call
heapifyon every internal node from the last one (n/2 − 1) down to the root. Leaves are already heaps. This takesO(n)in total, notO(n log n).extract
For
i = n − 1 … 1: swaparr[0](the max) witharr[i], thenheapify(0)on the heap of sizei. Each extraction isO(log n).
def heapify(arr, n, i):
largest = i
left, right = 2 * i + 1, 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:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest) # keep sinking the displaced value
def build_heap(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1): # internal nodes, bottom-up
heapify(arr, n, i)
def heap_sort(arr):
n = len(arr)
build_heap(arr)
print("max-heap:", *arr)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # max goes to the end
heapify(arr, i, 0) # restore the heap of size i
for arr in ([4, 10, 3, 5, 1, 12, 7], [50, 20, 10, 4, 15]):
heap_sort(arr)
print("sorted:", *arr)#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int largest = i, left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest); // keep sinking the displaced value
}
}
void show(const char* label, const vector<int>& v) {
cout << label;
for (int x : v) cout << " " << x;
cout << "\n";
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // build heap, bottom-up
show("max-heap:", arr);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]); // max goes to the end
heapify(arr, i, 0); // restore the heap of size i
}
}
int main() {
vector<vector<int>> tests = {{4, 10, 3, 5, 1, 12, 7}, {50, 20, 10, 4, 15}};
for (auto& arr : tests) {
heapSort(arr);
show("sorted:", arr);
}
}public class Main {
static void heapify(int[] arr, int n, int i) {
int largest = i, left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
heapify(arr, n, largest); // keep sinking the displaced value
}
}
static String join(int[] a) {
StringBuilder sb = new StringBuilder();
for (int x : a) sb.append(' ').append(x);
return sb.toString();
}
static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // build heap, bottom-up
System.out.println("max-heap:" + join(arr));
for (int i = n - 1; i > 0; i--) {
int t = arr[0]; arr[0] = arr[i]; arr[i] = t; // max goes to the end
heapify(arr, i, 0); // restore the heap of size i
}
}
public static void main(String[] args) {
int[][] tests = {{4, 10, 3, 5, 1, 12, 7}, {50, 20, 10, 4, 15}};
for (int[] arr : tests) {
heapSort(arr);
System.out.println("sorted:" + join(arr));
}
}
}function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest); // keep sinking the displaced value
}
}
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i); // build heap, bottom-up
console.log("max-heap:", arr.join(" "));
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // max goes to the end
heapify(arr, i, 0); // restore the heap of size i
}
}
for (const arr of [[4, 10, 3, 5, 1, 12, 7], [50, 20, 10, 4, 15]]) {
heapSort(arr);
console.log("sorted:", arr.join(" "));
}max-heap: 12 10 7 5 1 3 4
sorted: 1 3 4 5 7 10 12
max-heap: 50 20 10 4 15
sorted: 4 10 15 20 50Time O(n log n) in every case · Space O(1)
An optimisation of selection sort: the same extract the extreme, shrink the range loop, with an
O(log n)extraction instead ofO(n).Guaranteed
O(n log n)and in-place — the combination merge sort and quick sort each lack. The price: poor cache locality, so it is slower than quick sort in practice.Not stable: swapping the root with the last leaf can jump an element over equal keys.
Used as the fallback inside introsort (
std::sort) and wherever a worst-case guarantee matters. The heap itself is the DSA Basics → Heap topic.
Interview Q&A
Which sorting algorithm would you pick, and why?
What does stable mean, and which algorithms are stable?
Why is quick sort faster than merge sort in practice if both are O(n log n)?
When does quick sort degrade to O(n²), and how do you prevent it?
Can you sort in better than O(n log n)?
What is the difference between sort() and sorted() in Python?
Why does [10, 9, 1].sort() give [1, 10, 9] in JavaScript?
How many swaps does selection sort make, and why is that interesting?