Skip to content
Tutorials Center
My learning

Topics

Lesson 192 of 201 ยท Data Structures and Algorithms

Searching and Sorting Algorithms

Implement linear and binary search plus bubble, selection, insertion, merge, quick and heap sort in Java, with step-by-step traces, Big-O, stability and timings.

Searching and sorting are the two problems every programmer meets first and keeps meeting forever. Finding a user by ID, showing products cheapest first, merging two logs by timestamp, picking the median response time: each one is a search, a sort, or both. They're also the best place to learn how to think about algorithms, because the same data can be processed in ways that differ by a factor of a thousand in speed.

In this lesson you'll implement two searches and six sorting algorithms on plain int[] arrays, trace each one step by step, and then race them against each other with System.nanoTime. Along the way you'll learn the Big-O cost of each, what stability means and why it matters, and exactly what Arrays.sort and List.sort do for you. The Big-O vocabulary comes from Data Structures in Java.

The simplest search checks every element in turn until it finds a match. It works on any array, sorted or not, and costs O(n): double the data, double the time.

Java Linear search, with a comparison counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Returning -1 for "not found" is the convention String.indexOf and List.indexOf follow too. A missing value is the worst case: every element is checked. For one-off searches over small or unsorted data, linear search is perfectly fine, and with objects it's what list.contains(x) and list.indexOf(x) do internally (using equals).

If the array is sorted, you can do dramatically better. Look at the middle element. If it's the target, you're done. If the target is smaller, it can only be in the left half; if larger, only in the right half. Each comparison throws away half of what's left, so a million elements need at most 20 comparisons. That's O(log n).

Java Binary search with a trace of every step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Searching for 47 takes three steps (middle 34, then 58, then 47) instead of ten. Searching for 20 ends when low passes high: the range is empty, so the value isn't there. The details that make binary search notoriously easy to get wrong:

  • The loop condition is low <= high. With <, a one-element range is never checked and you miss targets at the edges.
  • Move past mid. Use mid + 1 and mid - 1. Setting low = mid can loop forever when low and high are neighbors.
  • Compute the midpoint safely. (low + high) / 2 overflows when both are above about 1.07 billion, producing a negative index. low + (high - low) / 2 (or (low + high) >>> 1) can't overflow. This exact bug sat in the JDK's own binary search for nine years.
  • The data must be sorted by the same order you compare with. On unsorted data, binary search returns wrong answers without any error.

Finding the first match and the insertion point

With duplicates, the basic version returns some matching index, not necessarily the first. A slightly different loop, often called lower bound, finds the first index whose value is greater than or equal to the target. It answers "is it there?", "where does the first copy start?" and "where would I insert it to keep the array sorted?" all at once.

Java Lower bound and Arrays.binarySearch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

lowerBound(scores, 20) returns 1, the first of the three 20s, and lowerBound(scores, 30) returns 4, the slot where 30 would be inserted. Here high starts one past the end and the loop uses low < high, because the answer can be values.length. Both versions are correct; just don't mix their conventions.

Arrays.binarySearch and Collections.binarySearch encode "not found" cleverly: they return -(insertionPoint) - 1, which is always negative. For 30, the insertion point is 4, so the result is โˆ’5. With duplicates, the JDK doesn't promise which match it returns. (See The Arrays Class for its other methods.)

Simple sorts: bubble, selection and insertion

The three classic O(nยฒ) sorts are slow on big inputs, but they're short, they sort in place with O(1) extra memory, and insertion sort in particular is genuinely useful on small or nearly sorted arrays. Each one prints the array after every outer pass, so you can watch it work.

Java Bubble, selection and insertion sort, pass by pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

How each one thinks:

  • Bubble sort walks the array swapping neighbors that are out of order. After each pass, the largest remaining value has "bubbled" to the end, so the sorted region grows from the right: after the first pass, 37 is in last place. The swapped flag stops early when a pass makes no swaps, so already sorted input costs only O(n). Bubble sort does the most swaps of the three and is almost never the right choice; it's taught because it's easy to see.
  • Selection sort finds the smallest value in the unsorted part and swaps it to the front. The sorted region grows from the left: 5 first, then 10, then 13. It always does about nยฒ/2 comparisons, even on sorted input, but at most n โˆ’ 1 swaps, which matters only when writes are very expensive.
  • Insertion sort takes the next value and slides it left into its place among the already sorted values, like sorting a hand of cards. Watch the pass where 13 arrives: 37, 29 and 14 each shift right, and 13 drops in after 10.

Trace insertion sort's fourth pass in detail. Before it, the first four values are sorted: [10, 14, 29, 37 | 13, 5].

Step Compare Action Array
take 13 current = 13 10 14 29 37 _ 5
j = 3 37 > 13 shift 37 right 10 14 29 _ 37 5
j = 2 29 > 13 shift 29 right 10 14 _ 29 37 5
j = 1 14 > 13 shift 14 right 10 _ 14 29 37 5
j = 0 10 > 13? no stop, place 13 at j + 1 10 13 14 29 37 5

Insertion sort's work depends on how far each element must travel. On nearly sorted data, each element moves a step or two, so the whole sort is close to O(n). That's why the JDK's sort algorithms switch to insertion sort for small chunks (a few dozen elements; the exact threshold depends on the algorithm and JDK version).

Merge sort

Merge sort is divide and conquer applied to sorting: split the array in half, sort each half (recursively), then merge the two sorted halves into one. Merging is easy because both halves are sorted: repeatedly take the smaller front element. An array of one element is already sorted, which is the base case of the recursion.

Java Merge sort with an indented recursion trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The indentation shows the recursion tree. The array is split until each piece has one element; then the merges happen on the way back up, building sorted runs of 2, 3, 4 and finally 7 elements. The last merge combines [27, 38, 43] with [3, 9, 10, 82]:

Left front Right front Take Output so far
27 3 3 3
27 9 9 3 9
27 10 10 3 9 10
27 82 27 3 9 10 27
38 82 38 3 9 10 27 38
43 82 43 3 9 10 27 38 43
(empty) 82 82 3 9 10 27 38 43 82

Why is merge sort O(n log n)? Halving n elements down to size 1 takes logโ‚‚ n levels, and each level merges a total of n elements. That holds for every input, sorted, reversed or random, so merge sort has no bad case. Its costs are the O(n) buffer and the copying. The single buffer is allocated once and passed down; allocating a new array in every call would work but create lots of garbage.

Quicksort

Quicksort is also divide and conquer, but it does the hard work before recursing. Pick a pivot value, then partition the array: move everything smaller than the pivot to its left and everything larger to its right. The pivot is now in its final position. Recursively sort the two sides; no merge step is needed.

Java Quicksort with Lomuto partitioning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The first partition uses the last value, 5, as the pivot. It scans the array once; every value smaller than 5 (2, 4, 3, 1) is swapped into the growing "small" region at the front. Then 5 is swapped in right after them, landing at index 4, its final place. Everything left of it is smaller, everything right of it is larger, and the two sides are sorted independently.

Quicksort is O(n log n) on average and usually the fastest comparison sort in practice: it works in place, scans memory sequentially, and has a tight inner loop. But it has a weakness. If the pivot is always the smallest or largest value, each partition only peels off one element, and the cost becomes O(nยฒ). With "last element as pivot", that happens on input that is already sorted, a very common case. Real implementations defend against it:

  • Choose the pivot randomly, or as the median of three (first, middle and last values).
  • Use three-way partitioning (less than, equal to, greater than) so arrays with many duplicates don't degrade.
  • Switch to insertion sort for tiny ranges and recurse into the smaller side first, which bounds the stack depth to O(log n).

The JDK's Arrays.sort(int[]) is a dual-pivot quicksort that does all of this (and switches to heap sort if recursion gets too deep), so its worst case is O(n log n).

Heap sort

Heap sort uses the binary heap from Data Structures in Java: an array arranged as a complete binary tree in which every parent is at least as large as its children (a max-heap). The children of index i are at 2i + 1 and 2i + 2, so no node objects are needed.

The algorithm has two phases. First, heapify the array so the largest value is at index 0. Then repeat: swap the root to the end of the array, shrink the heap by one, and sift down the new root to restore the heap property. Each sift-down takes O(log n), so the whole sort is O(n log n), in place, with no bad cases.

Java Heap sort with sift-down

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

After phase 1, the array is [10, 5, 8, 4, 1, 3, 7]. Read it as a tree: 10 is the root, its children are 5 and 8 (indexes 1 and 2), 5's children are 4 and 1, and 8's children are 3 and 7. Every parent beats its children. In phase 2, the sorted region grows from the right: 10, then 8, then 7 move into place.

Heap sort's guarantees look ideal on paper: O(n log n) worst case and O(1) extra memory. In practice it's slower than quicksort and merge sort because it jumps around the array (parent to child is a jump of i positions), which the CPU cache dislikes. It's also not stable. The same heap idea is more often used for priority queues and top-k problems, which is what PriorityQueue does.

Stability

A sort is stable if elements that compare as equal keep their original relative order. With plain ints you can't tell the difference, but with objects you often can: sort orders by date, then sort the result by customer with a stable sort, and each customer's orders stay in date order. That's how multi-column sorting in spreadsheets works.

Java A stable and an unstable sort on the same data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The stable sorts keep each grade's students alphabetical: Ben, Dev, Fay and then Ana, Cleo, Eli. Selection sort ends with Ana, Eli, Cleo. Trace it: the first swap moves Ben to the front and sends Ana to slot 1; the second brings Dev forward and sends Ana to slot 3; the third brings Fay forward and sends Cleo from slot 2 all the way to the end, jumping over Ana and Eli. Each swap is correct for sorting, but it ignores where equal elements were.

Stability comes from small details. Insertion sort is stable because it uses > and never moves an element past an equal one; change it to >= and it becomes unstable. Merge sort is stable because its merge takes from the left half on ties (<=). Quicksort and heap sort move elements over long distances and are not stable.

Algorithm Best Average Worst Extra memory Stable
Bubble sort (with early exit) O(n) O(nยฒ) O(nยฒ) O(1) yes
Selection sort O(nยฒ) O(nยฒ) O(nยฒ) O(1) no
Insertion sort O(n) O(nยฒ) O(nยฒ) O(1) yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) yes
Quicksort O(n log n) O(n log n) O(nยฒ) O(log n) stack no
Heap sort O(n log n) O(n log n) O(n log n) O(1) no

No comparison sort can beat O(n log n) in the worst case: there are n! possible orderings to tell apart, and each comparison gives one bit of information, so you need about logโ‚‚(n!) โ‰ˆ n logโ‚‚ n comparisons. Algorithms such as counting sort and radix sort go faster only by not comparing at all; they exploit the structure of the keys (small integers, fixed-length strings).

Racing the algorithms

Big-O predicts how algorithms scale; a stopwatch shows what happens on a real machine. This benchmark sorts the same random data with each algorithm. The quadratic sorts get 5,000 elements and the fast sorts get 200,000, because bubble sort on 200,000 elements would take far longer than the run limit.

Java Timing six sorts with System.nanoTime

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Exact numbers change from run to run and machine to machine, but the pattern is always the same:

  • The three quadratic sorts take milliseconds on just 5,000 elements. Bubble sort is the slowest by a wide margin; insertion sort is the fastest of the three because its inner loop does little work and stops early.
  • Merge sort finishes 5,000 elements in well under a millisecond, and sorts 200,000 elements, 40 times more data, in tens of milliseconds: about what the quadratic sorts needed for just 5,000.
  • Among the fast sorts, quicksort and merge sort are close, heap sort is noticeably slower (its cache-unfriendly jumps), and Arrays.sort beats them all.

The benchmark follows a few rules that keep timings honest: it uses a fixed seed so every run sorts the same data, sorts a fresh clone() each time (sorting already sorted data would flatter some algorithms), does a warm-up run so the JIT compiler has compiled the code, and verifies the result. Even so, a single run in a shared sandbox is noisy. For serious measurements, use JMH, as Java Performance Tips explains.

The quicksort here also shows two of the defenses from earlier: it uses the middle element as the pivot (so sorted input is fast) and recurses only into the smaller side, looping on the larger one, which keeps the stack depth at O(log n).

What the JDK uses

In real code, never hand-write a sort. Use the library:

Java
Arrays.sort(numbers);                           // int[], double[], ...: dual-pivot quicksort
Arrays.sort(words);                             // Object[]: TimSort, stable
Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);
list.sort(Comparator.comparing(Person::lastName)
              .thenComparing(Person::firstName)); // TimSort, stable
Collections.sort(list);                         // same as list.sort(null)
Arrays.parallelSort(bigArray);                  // splits work across cores for huge arrays
  • Primitive arrays use dual-pivot quicksort. Stability doesn't matter for primitives (two equal ints are indistinguishable), so the JDK picks the fastest in-place algorithm.
  • Object arrays and lists use TimSort, a merge sort hybrid that finds already sorted runs in the data and merges them, using insertion sort for short runs. It's stable, O(n log n) in the worst case, and close to O(n) on partly sorted input, which is very common in real data.
  • Searching: Arrays.binarySearch and Collections.binarySearch for sorted data; TreeMap.floorKey/ceilingKey when the data changes while you search (TreeMap and TreeSet); a HashSet or HashMap when you only need "is it there?" in O(1).
  • Comparators define the order for objects; Sorting with Comparable and Comparator covers them in depth, including why compareTo must be consistent.

If you write a comparator by subtracting, as in (a, b) -> a.age() - b.age(), large values can overflow and produce the wrong sign. Use Integer.compare(a, b) or Comparator.comparingInt(...). TimSort may even throw IllegalArgumentException: Comparison method violates its general contract! when a comparator is inconsistent.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the maximum number of comparisons binary search needs on a sorted array of 1,000 elements?

    Each comparison halves the remaining range, and 2^10 = 1,024 is at least 1,000, so 10 comparisons always suffice.
  2. 2. Arrays.binarySearch(a, 25) on int[] a = {10, 20, 30, 40} returns what?

    25 is not present; its insertion point is index 2 (before 30). The method returns -(insertionPoint) - 1 = -3.
  3. 3. Which algorithm sorts an already sorted array of n elements in O(n) time?

    Insertion sort's inner loop stops immediately when each element is already in place, so it does one comparison per element. Selection sort always scans the whole unsorted part, and last-element quicksort degrades to O(nยฒ) on sorted input.
  4. 4. You sort a list of orders by date, then sort the result by customer. When will each customer's orders still be in date order?

    A stable sort keeps equal elements (same customer) in their existing relative order, which is date order from the first sort. List.sort uses stable TimSort. A combined comparator with thenComparing also works.
  5. 5. Why does merge sort take O(n log n) time on every input?

    Splitting always divides the array evenly, giving log2 n levels, and merging all the pieces at one level costs O(n). Unlike quicksort, nothing about the input can make the split uneven.

Summary

  • Linear search works on any data in O(n); binary search needs sorted data and runs in O(log n). Use low <= high, move past mid, and compute mid without overflow.
  • Lower bound finds the first index whose value is at least the target, which is also the insertion point; Arrays.binarySearch returns -(insertionPoint) - 1 when the key is missing.
  • Bubble, selection and insertion sort are O(nยฒ); insertion sort is the useful one, fast on small or nearly sorted data.
  • Merge sort is a stable O(n log n) sort that needs O(n) extra memory; quicksort is usually fastest but needs good pivots to avoid O(nยฒ); heap sort is O(n log n) in place but unstable and cache-unfriendly.
  • A stable sort keeps equal elements in their original order, which makes multi-key sorting work.
  • Time code with a fixed seed, fresh copies, warm-up runs and a correctness check; use JMH for serious benchmarks.
  • In real code use Arrays.sort (dual-pivot quicksort for primitives, stable TimSort for objects), List.sort with a Comparator, and Arrays.binarySearch.

Next: Graphs, Recursion and Backtracking, where you'll explore graphs with BFS and DFS, find shortest paths with Dijkstra's algorithm, and solve puzzles with backtracking.