Stage 5: Data structures and algorithms, lesson 2 of 5

Sorting and searching

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

In real code, use the library: Arrays.sort, List.sort or Collections.sort. Java uses dual-pivot quicksort for primitives and TimSort (stable, O(n log n)) for objects.

Interviews, and your own understanding, still need the classics:

  • Bubble and insertion sort: O(n²). Insertion sort is fast on small, nearly sorted arrays.
  • Merge sort: split in halves, sort each, merge. Always O(n log n) and stable, but needs O(n) extra space.
  • Quick sort: pick a pivot, partition, recurse. O(n log n) on average, O(n²) in the worst case, sorts in place.

Binary search finds an item in a sorted array in O(log n): compare with the middle, discard half, repeat. It also answers questions like "the first position where the value is at least x", which appear in many interview problems.

Example

Java
static void mergeSort(int[] a, int lo, int hi) {            // sorts a[lo..hi)
    if (hi - lo < 2) return;
    int mid = (lo + hi) >>> 1;
    mergeSort(a, lo, mid);
    mergeSort(a, mid, hi);
    int[] merged = new int[hi - lo];
    int i = lo, j = mid, k = 0;
    while (i < mid && j < hi) merged[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < mid) merged[k++] = a[i++];
    while (j < hi) merged[k++] = a[j++];
    System.arraycopy(merged, 0, a, lo, merged.length);
}

static int firstAtLeast(int[] sorted, int target) {         // binary search: lower bound
    int lo = 0, hi = sorted.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;                           // avoids int overflow
        if (sorted[mid] < target) lo = mid + 1; else hi = mid;
    }
    return lo;                                               // equals length if none
}

int[] marks = {72, 38, 91, 55, 64};
mergeSort(marks, 0, marks.length);                           // [38, 55, 64, 72, 91]
System.out.println(firstAtLeast(marks, 60));                 // 2

Common mistake

Running binary search on unsorted data. It silently returns wrong answers; sort first or use a different structure.

Under the hood

(lo + hi) / 2 overflows when both numbers are large; (lo + hi) >>> 1 or lo + (hi - lo) / 2 doesn't. This exact bug sat in the JDK's own binary search for years. Stability matters when you sort by several keys in passes. For top-k problems you don't need a full sort: a PriorityQueue of size k is O(n log k).

Check yourself

Binary search requires the data to be…

How this connects

Where this leads

You've reached the end of this thread. Try a learning path for what's next.

Part of Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.