SyntaxPilot
Courses/Java/Lesson 49
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Java · Lesson 49 of 51

DSA 3: sorting, binary search, dynamic programming

queued

These are the notes for Java episode 49, the last part of the DSA series. A teacher lines up a class by marks: swapping neighbours (bubble sort) works, but takes seconds for a lakh students, while merge sort (and Arrays.sort) takes milliseconds. Sorted data pays off when searching: binary search finds one roll number among 10 lakh in about 20 steps, as long as every step shrinks the range. Finally, counting the ways up a staircase with plain recursion makes 33 crore calls for 40 steps, and dynamic programming (memoization or a table) cuts that to under a hundred. Every example was run with javac 21.

Timings depend on the machine. The outputs below are real runs; your millisecond numbers will differ.

Sorting

Sorting means putting data in order. Real-life problem: lining up the class by marks.

Bubble sort

Compare neighbours, swap them if they're in the wrong order, and walk the line again and again. Each walk is a pass; after each pass the biggest remaining value has "bubbled" to the end.

import java.util.Arrays;

public class Main {
    static void bubbleSort(int[] a) {
        for (int pass = 0; pass < a.length - 1; pass++)
            for (int i = 0; i < a.length - 1 - pass; i++)
                if (a[i] > a[i + 1]) {                     // neighbours in the wrong order?
                    int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;   // swap them
                }
    }
    public static void main(String[] args) {
        int[] marks = {72, 45, 91, 38, 66, 85, 50};
        bubbleSort(marks);
        System.out.println(Arrays.toString(marks));
    }
}

Output:

[38, 45, 50, 66, 72, 85, 91]

1 lakh students

import java.util.Arrays;
public class Main {
    static void bubbleSort(int[] a) {
        for (int pass = 0; pass < a.length - 1; pass++)
            for (int i = 0; i < a.length - 1 - pass; i++)
                if (a[i] > a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
    }
    public static void main(String[] args) {
        int n = 100_000;                                         // 1 lakh students
        int[] marks = new int[n], copy = new int[n];
        for (int i = 0; i < n; i++) marks[i] = copy[i] = (int) ((i * 7919L) % 1000);
        long t0 = System.currentTimeMillis();
        bubbleSort(marks);
        System.out.println("bubble sort:  " + (System.currentTimeMillis() - t0) + " ms");
        long t1 = System.currentTimeMillis();
        Arrays.sort(copy);                                       // Java's built-in sort
        System.out.println("Arrays.sort:  " + (System.currentTimeMillis() - t1) + " ms");
    }
}

Output (one run):

bubble sort:  6657 ms
Arrays.sort:  23 ms

Bubble sort's two nested loops make about n²/2 comparisons: O(n²). Arrays.sort is O(n log n).

Merge sort

Real-life example: two teachers, two sorted piles.

Sorting answer sheets Merge sort
split the pile in half, give each half to a helper divide: mid = (lo + hi) / 2
each helper splits again, down to single sheets recursion (episode 12): one sheet is already sorted
merge two sorted piles: always take the smaller top sheet merge: one pass, O(n)
a lakh sheets can only be halved about 17 times n work × log n levels = O(n log n)
public class Main {
    static void mergeSort(int[] a, int lo, int hi) {          // sorts a[lo..hi)
        if (hi - lo < 2) return;                               // 0 or 1 item: already sorted
        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid);                                 // sort the left half
        mergeSort(a, mid, hi);                                 // sort the right half
        int[] out = new int[hi - lo];
        int i = lo, j = mid, k = 0;
        while (i < mid && j < hi) out[k++] = a[i] <= a[j] ? a[i++] : a[j++];   // take the smaller
        while (i < mid) out[k++] = a[i++];
        while (j < hi) out[k++] = a[j++];
        System.arraycopy(out, 0, a, lo, out.length);
    }
    public static void main(String[] args) {
        int[] marks = {72, 45, 91, 38, 66, 85, 50};
        mergeSort(marks, 0, marks.length);
        System.out.println(java.util.Arrays.toString(marks));
    }
}

Output:

[38, 45, 50, 66, 72, 85, 91]
  • mergeSort(a, lo, hi) sorts a[lo..hi): lo included, hi excluded.
  • The merge takes the smaller front value with a[i] <= a[j] ? a[i++] : a[j++]; using <= keeps equal values in their original order, which makes merge sort stable.
  • Merge sort needs O(n) extra space for the out arrays.
  • In real code, call Arrays.sort: a tuned dual-pivot quicksort for primitive arrays, and TimSort (a merge-sort variant, stable) for objects and Collections.sort.
Algorithm Time (worst) Extra space Stable
bubble sort O(n²) O(1) yes
selection sort O(n²) O(1) no
insertion sort O(n²), O(n) if nearly sorted O(1) yes
merge sort O(n log n) O(n) yes
quicksort O(n log n) on average, O(n²) worst O(log n) no

Real-life problem: finding one roll number in a thick register. Page by page is linear search, O(n). Opening the middle and keeping only the half that can contain the number is binary search: each step halves the range, O(log n). It only works on sorted data.

public class Main {
    public static void main(String[] args) {
        int n = 1_000_000;
        int[] rolls = new int[n];
        for (int i = 0; i < n; i++) rolls[i] = 2 * i + 1;     // sorted roll numbers
        int want = 1_999_999;                                 // the very last one
        int linear = 0;
        for (int r : rolls) { linear++; if (r == want) break; }
        int lo = 0, hi = n - 1, binary = 0;
        while (lo <= hi) {
            binary++;
            int mid = lo + (hi - lo) / 2;                     // the middle page
            if (rolls[mid] == want) break;
            if (rolls[mid] < want) lo = mid + 1;              // throw away the left half
            else hi = mid - 1;                                // throw away the right half
        }
        System.out.println("linear search: " + linear + " steps\nbinary search: " + binary + " steps");
    }
}

Output:

linear search: 1000000 steps
binary search: 20 steps
  • lo and hi mark the part of the array still in play.
  • mid = lo + (hi - lo) / 2 gives the same middle as (lo + hi) / 2 but can't overflow when lo + hi is bigger than Integer.MAX_VALUE.
  • 2²⁰ ≈ 10 lakh, so 20 steps; 100 crore items would need only about 30.
  • Built in: Arrays.binarySearch(array, key) and Collections.binarySearch(list, key) return the index, or a negative number if the key is missing.

The lo = mid bug

public class Main {
    static int find(int[] a, int want) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == want) return mid;
            if (a[mid] < want) lo = mid;           // forgot the + 1
            else hi = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] rolls = {11, 23, 35, 47, 59};
        System.out.println("47 is at index " + find(rolls, 47));
        System.out.println("50 is at index " + find(rolls, 50));
    }
}

Output: 47 is at index 3, then nothing until Time Limit Exceeded.

Searching for 50: lo = 3, hi = 4, mid = 3, 47 < 50, so lo = mid = 3: nothing changes, forever. Every step must shrink the range: lo = mid + 1, hi = mid - 1.

Dynamic programming

Real-life problem: ways up the ghat steps, taking 1 or 2 steps at a time. The last move came from step n − 1 or from step n − 2, so ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1.

Plain recursion

public class Main {
    static long calls = 0;
    static long ways(int n) {                       // ways to climb n steps, 1 or 2 at a time
        calls++;
        if (n <= 1) return 1;
        return ways(n - 1) + ways(n - 2);           // last move was 1 step, or 2 steps
    }
    public static void main(String[] args) {
        for (int n : new int[]{5, 30, 40}) {
            calls = 0;
            long w = ways(n);
            System.out.println(n + " steps: " + w + " ways, " + calls + " calls");
        }
    }
}

Output (takes a moment for 40):

5 steps: 8 ways, 15 calls
30 steps: 1346269 ways, 2692537 calls
40 steps: 165580141 ways, 331160281 calls

40 steps: 33 crore calls. ways(40) calls ways(39) and ways(38); ways(39) calls ways(38) again, and so on: the same sub-problems are solved again and again. The number of calls roughly multiplies by 1.6 for every extra step: exponential time, about O(2ⁿ).

Real-life example: write the answer down once.

In a maths exam Dynamic programming
write each answer in the margin the first time memoization: store each result (top-down)
needed again? look it up a cache hit, O(1)
or fill a table from step 0 upwards tabulation: fill dp[i] from smaller cells (bottom-up)

Dynamic programming (DP) solves a problem by breaking it into overlapping sub-problems and solving each one only once. It applies when the best answer is built from answers to smaller sub-problems (optimal substructure).

Memoization (top-down)

public class Main {
    static long calls = 0;
    static long[] memo = new long[100];             // memo[n] = answer for n steps, 0 = not yet
    static long ways(int n) {
        calls++;
        if (n <= 1) return 1;
        if (memo[n] != 0) return memo[n];           // solved before: just look it up
        return memo[n] = ways(n - 1) + ways(n - 2);
    }
    public static void main(String[] args) {
        for (int n : new int[]{5, 30, 40, 90}) {
            calls = 0;
            memo = new long[100];                   // a fresh notebook each time
            long w = ways(n);
            System.out.println(n + " steps: " + w + " ways, " + calls + " calls");
        }
    }
}

Output:

5 steps: 8 ways, 9 calls
30 steps: 1346269 ways, 59 calls
40 steps: 165580141 ways, 79 calls
90 steps: 4660046610375530309 ways, 179 calls

79 calls instead of 33 crore: each n is computed once, O(n) time, O(n) space. return memo[n] = ... stores the value and returns it in one step. Zero means "not solved yet", which works here because every real answer is at least 1.

Tabulation (bottom-up)

public class Main {
    public static void main(String[] args) {
        int n = 90;
        long[] dp = new long[n + 1];                // dp[i] = ways to reach step i
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];          // fill the table from the bottom up
        System.out.println("90 steps: " + dp[n] + " ways");
    }
}

Output:

90 steps: 4660046610375530309 ways

No recursion at all, so no StackOverflowError for big n. Since each cell only needs the two before it, two variables are enough: O(1) space. (long holds up to about 9.2 × 10¹⁸; ways(91) would still fit, ways(92) would overflow.)

Today's Big-O, side by side

Before After
bubble sort O(n²) merge sort / Arrays.sort O(n log n)
linear search O(n) binary search O(log n), on sorted data
plain recursion O(2ⁿ) DP O(n)

Common mistakes (and what you see)

Mistake What you see Why Fix
bubble sort on 1 lakh items no error: seconds instead of milliseconds O(n²) Arrays.sort
if (a[mid] < want) lo = mid; Time Limit Exceeded the range stops shrinking lo = mid + 1
binary search on unsorted data no error: -1 for values that are there halving needs order sort first
int mid = (lo + hi) / 2; on huge arrays a negative mid, then ArrayIndexOutOfBoundsException lo + hi overflows lo + (hi - lo) / 2
recursion with overlapping sub-problems no error: crores of calls the same work again and again memo array or dp table
deep recursion for big n java.lang.StackOverflowError one frame per call bottom-up table

Mini project: the best snacks for the class party

A 0/1 knapsack: each snack has a price and a "joy" score; buy each at most once and get the most joy within Rs 100.

public class Main {
    public static void main(String[] args) {
        String[] snack = {"samosa", "vada pav", "dhokla", "kachori", "jalebi"};
        int[] price = {20, 25, 40, 30, 35};
        int[] joy   = {30, 35, 50, 40, 45};               // how much the class will enjoy it
        int budget = 100;
        // best[b] = most joy with budget b, each snack bought at most once (0/1 knapsack)
        int[] best = new int[budget + 1];
        for (int i = 0; i < snack.length; i++)
            for (int b = budget; b >= price[i]; b--)       // backwards: each snack used once
                best[b] = Math.max(best[b], best[b - price[i]] + joy[i]);
        System.out.println("Most joy within Rs " + budget + ": " + best[budget]);
    }
}

Output:

Most joy within Rs 100: 130

best[b] is the most joy possible with budget b. Looping the budget backwards makes sure each snack is used at most once. The winning set is dhokla, jalebi and vada pav: Rs 100 for 130 joy. Time O(snacks × budget).

Practice

  1. Selection sort, and count its swaps.
  2. Binary search for the first position of a value.
  3. Steps of 1, 2 or 3: count the ways with DP.
  4. Coin change: fewest coins for Rs 63 with coins 1, 2, 5, 10, 20.
Solution 1
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] marks = {72, 45, 91, 38, 66, 85, 50};
        int swaps = 0;
        for (int i = 0; i < marks.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < marks.length; j++)
                if (marks[j] < marks[min]) min = j;          // find the smallest of the rest
            if (min != i) {
                int t = marks[i]; marks[i] = marks[min]; marks[min] = t;
                swaps++;
            }
        }
        System.out.println(Arrays.toString(marks) + " with " + swaps + " swaps");
    }
}

Output:

[38, 45, 50, 66, 72, 85, 91] with 3 swaps

Selection sort finds the smallest remaining value and swaps it into place: O(n²) comparisons but at most n − 1 swaps.

Solution 2
public class Main {
    static int firstIndex(int[] a, int want) {
        int lo = 0, hi = a.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] >= want) {
                if (a[mid] == want) ans = mid;               // a candidate: keep looking left
                hi = mid - 1;
            } else lo = mid + 1;
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] marks = {38, 45, 50, 66, 66, 66, 72, 91};
        System.out.println("first 66 at index " + firstIndex(marks, 66));
        System.out.println("first 70 at index " + firstIndex(marks, 70));
    }
}

Output:

first 66 at index 3
first 70 at index -1

When a[mid] equals the value, record it and keep searching the left half.

Solution 3
public class Main {
    public static void main(String[] args) {
        int n = 10;
        long[] dp = new long[n + 1];
        dp[0] = 1;                                         // one way to stand still
        for (int i = 1; i <= n; i++)
            for (int step = 1; step <= 3; step++)
                if (i - step >= 0) dp[i] += dp[i - step];   // last move: 1, 2 or 3 steps
        System.out.println("10 steps, moves of 1-3: " + dp[n] + " ways");
    }
}

Output:

10 steps, moves of 1-3: 274 ways
Solution 4
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20};
        int amount = 63;
        int[] fewest = new int[amount + 1];                 // fewest[a] = fewest coins to make a
        Arrays.fill(fewest, Integer.MAX_VALUE);
        fewest[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && fewest[a - c] != Integer.MAX_VALUE)
                    fewest[a] = Math.min(fewest[a], fewest[a - c] + 1);
        System.out.println("Fewest coins for Rs 63: " + fewest[amount]);
    }
}

Output:

Fewest coins for Rs 63: 5

20 + 20 + 20 + 2 + 1. (Taking the biggest coin first happens to work for Indian coins, but not for every coin system: with coins 1, 3, 4 and amount 6, greedy gives 4+1+1 while DP finds 3+3.)

Quick quiz

Ten lakh sorted values. At most how many steps does binary search need?

A. about 10 B. about 20 C. about 1,000 D. about 5,00,000

Answer

B. About 20. Each step halves the range, and 2²⁰ ≈ 10 lakh.

Interview questions

  1. Why is merge sort O(n log n)? log n levels of halving, and each level does O(n) merging work.
  2. Merge sort vs quicksort? Merge sort: guaranteed O(n log n), stable, O(n) extra space. Quicksort: in-place and fast on average, O(n²) worst case.
  3. What is a stable sort? Equal elements keep their original relative order.
  4. Which sort does Java use? Dual-pivot quicksort for primitive arrays; TimSort for objects.
  5. Conditions for binary search? Sorted (or monotonic) data with random access.
  6. How do you avoid overflow when computing mid? lo + (hi - lo) / 2.
  7. What is dynamic programming? Solving overlapping sub-problems once each and reusing the answers.
  8. Memoization vs tabulation? Top-down recursion with a cache vs bottom-up loops filling a table.
  9. How do you spot a DP problem? "Count the ways", "minimum/maximum", choices at each step, and a recursive solution that repeats sub-problems.

Glossary

Term Meaning
Sorting putting data in order
Pass one walk through the data
Bubble sort swap out-of-order neighbours, pass after pass; O(n²)
Selection sort repeatedly move the smallest remaining value into place; O(n²)
Merge sort split in half, sort each half, merge; O(n log n)
Divide and conquer solve by splitting into smaller copies of the same problem
Merge combine two sorted lists into one sorted list
Stable sort equal values keep their original order
TimSort the stable merge-based sort Java uses for objects
Linear search check items one by one; O(n)
Binary search halve a sorted range each step; O(log n)
lo, hi, mid the bounds of the range in play, and its middle
Integer overflow a value too big for int, wrapping to negative
Sub-problem a smaller version of the same problem
Overlapping sub-problems the same sub-problem needed many times
Optimal substructure the best answer is built from best answers to sub-problems
Exponential time work that multiplies with each extra step, e.g. O(2ⁿ)
Dynamic programming solve each overlapping sub-problem once and reuse it
Memoization top-down DP: cache results of recursive calls
Tabulation bottom-up DP: fill a table in order
Knapsack choose items with costs and values to maximise value within a budget

Summary

  • Bubble sort is O(n²); merge sort divides, sorts and merges in O(n log n); use Arrays.sort in real code.
  • Binary search finds a value in sorted data in O(log n) steps (about 20 for 10 lakh). Every step must shrink the range: lo = mid + 1, hi = mid - 1.
  • Recursion that repeats the same sub-problems explodes. Dynamic programming solves each once: memoization (top-down) or tabulation (bottom-up).
  • That completes DSA parts 1 to 3: Big-O, two pointers, sliding windows, core data structures, sorting, searching and DP.
  • Next episode: the capstone project, a library management system.