Java DSA Notes: Sorting, Searching &
Complexity
1. Big-O Notation
Big-O describes how an algorithm's running time or space grows as input size n grows, ignoring
constant factors and lower-order terms. It answers "what happens as n gets large", not "how fast is
this on my machine today". Common orders from fastest to slowest growth: O(1) constant, O(log n)
logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(2^n) exponential, O(n!)
factorial.
2. Bubble, Selection, Insertion Sort (O(n^2))
These simple sorts are rarely used in production but are important for building intuition. Bubble sort
repeatedly swaps adjacent out-of-order elements. Selection sort repeatedly finds the minimum of
the unsorted portion and swaps it into place. Insertion sort builds the sorted portion one element at a
time, similar to how you sort playing cards in your hand -- it is actually efficient (close to O(n)) on
nearly-sorted data.
void insertionSort(int[] a) {
for (int i = 1; i < [Link]; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
3. Merge Sort (O(n log n), stable)
A divide-and-conquer algorithm: split the array in half, recursively sort each half, then merge the two
sorted halves. The recursion depth is log n and merging each level costs O(n), giving O(n log n)
total. Merge sort is stable (equal elements keep their relative order) and guarantees O(n log n) even
in the worst case, but needs O(n) extra space for the merge step.
void mergeSort(int[] a, int lo, int hi) {
if (hi - lo <= 1) return;
int mid = (lo + hi) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid, hi);
int[] tmp = new int[hi - lo];
int i = lo, j = mid, k = 0;
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++];
[Link](tmp, 0, a, lo, [Link]);
}
4. Quicksort (O(n log n) average, O(n^2) worst case)
Pick a pivot, partition the array so smaller elements go left and larger go right, then recursively sort
each side. Quicksort is typically faster in practice than merge sort due to better cache locality and
in-place partitioning (no extra array), but its worst case is O(n^2) if the pivot choice is consistently
bad (e.g. always picking the first element on an already-sorted array). Randomized pivot selection
avoids this in practice.
void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; }
}
int t = a[i]; a[i] = a[hi]; a[hi] = t;
quickSort(a, lo, i - 1);
quickSort(a, i + 1, hi);
}
5. Java's Built-in Sorts
[Link]() on primitive arrays uses a dual-pivot quicksort variant (O(n log n) average, in-place).
[Link]() on Object arrays, and [Link](), use TimSort -- a hybrid of merge sort and
insertion sort that is stable and performs especially well on partially-sorted real-world data. Use a
custom Comparator when sorting objects by a specific field.
int[] nums = {5, 3, 1, 4};
[Link](nums); // dual-pivot quicksort
List<String> words = new ArrayList<>([Link]("banana", "apple"));
[Link]([Link]());
[Link]((a, b) -> [Link]() - [Link]()); // by length, descending
6. Binary Search (O(log n))
Requires a sorted array. Repeatedly compare the target to the middle element and discard half the
remaining search space each time. A common bug is (lo + hi) / 2 overflowing for very large arrays --
use lo + (hi - lo) / 2 instead.
int binarySearch(int[] a, int target) {
int lo = 0, hi = [Link] - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
7. Binary Search on the Answer
A powerful pattern beyond searching a static array: when a problem asks for the
minimum/maximum value satisfying some monotonic condition (e.g. "minimum speed to finish in
time", "smallest capacity to ship packages within D days"), binary search over the range of possible
answers, using a feasibility check at each guess.
// Template: find smallest x in [lo, hi] such that feasible(x) is true
int lo = 1, hi = maxPossible;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
8. Complexity Reference Table
Access by index (array): O(1). Search (unsorted): O(n). Search (sorted, binary search): O(log n).
Insert/delete at end of ArrayList: O(1) amortized. Insert/delete in middle of ArrayList: O(n). HashMap
get/put: O(1) average, O(n) worst case (hash collisions). TreeMap get/put: O(log n).
Bubble/selection/insertion sort: O(n^2). Merge/quick/heap sort: O(n log n) (quicksort O(n^2) worst
case). Binary search: O(log n).
9. Practice Problems to Revisit
Binary Search, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Merge
Intervals, Kth Largest Element in an Array, Sort Colors (Dutch National Flag), Capacity To Ship
Packages Within D Days, Koko Eating Bananas, Median of Two Sorted Arrays.