Searching and sorting algorithms

Two jobs turn up in almost every program: finding one item in a pile of data, and putting the pile in order. The contact list on your phone does both, keeping names in alphabetical order and jumping to the one you type. This lesson builds the classic algorithms for each job by hand, traces them one step at a time, and measures them with Big-O. Then it opens up the sorts that come with Java, which are the ones you will call in real code.

Linear search: check every item#

Start with the plainest way to find something. A teacher has a row of test scores in no particular order and wants to know where the 88 is. The only sure method is to look at the first score, then the next, then the next, until 88 turns up or the scores run out. That is linear search: walk the array from the front and compare each item with the target, the value you are looking for.

The method below returns the index where it finds the target, or -1 if the target is not there. No real index is negative, so -1 can never be mistaken for a position. Press Run and watch the arrow i walk along the array.

This prints 3 and then -1. Finding 88 took four comparisons, because 88 sits at index 3. Proving that 100 is missing took six: the loop had to check every score before it could give up.

In the worst case linear search compares all n items, so it is O(n): double the number of scores and you double the worst case. In return it asks nothing of the data. The items can be in any order, and the search can start straight away. That makes it the right tool for small arrays, for data you search only once, and for data in no order at all. ArrayList's indexOf method works exactly this way, -1 and all.

Binary search: halve what is left#

Try a guessing game with a friend. They think of a whole number from 1 to 100 and answer each guess with “higher” or “lower”. Guessing 1, 2, 3 and so on could take 100 guesses. Guess 50 first, though, and whatever they answer, half the numbers are gone. Keep guessing the middle of what is left and you never need more than 7 guesses.

Binary search plays that game on a sorted array. Two variables, lo and hi, mark the stretch of the array where the target could still be. Each round looks at the item halfway between them, at index mid, and compares it with the target:

• If the middle item is the target, the search is over.
• If the middle item is smaller than the target, the target can only be to its right, so lo moves to mid + 1.
• If the middle item is bigger, the target can only be to its left, so hi moves to mid - 1.

When lo passes hi, nothing is left to search, and the target is not in the array. Here it is on a sorted row of locker numbers. Open the trace: the arrows lo and hi under the array close in, and the call stack shows mid jumping between them.

It prints 6, then -1. Finding 30 takes two looks. The middle of all nine lockers is 21, at index 4, which is too small, so lo jumps to 5. The middle of indexes 5 to 8 is index 6, which holds 30. Searching for 5 takes three looks, and then hi drops below lo and the method gives up with -1.

Now drive it yourself. Pick a target, press Next look, and watch the count of numbers still in play shrink. Try a number that is missing, too.

Key idea

Binary search throws away half of what is left with every look. That makes it O(log n): even a million sorted items need at most 20 looks. The price is that the data must be sorted first.

Why the data must be sorted#

Every step rests on one assumption: everything left of the middle is smaller and everything right of it is bigger. That is what lets binary search drop half the array without looking at it. When the data is not sorted, the assumption is false, and the search can throw away the half that holds the answer. Here is the same method on numbers in no order.

30 is right there at index 0, yet the method prints -1. The first look lands on 8, in the middle. 8 is smaller than 30, so in a sorted array 30 would have to be further right, and the search drops the whole left side, 30 included. Nothing crashes and no warning appears; the method simply returns a wrong answer.

How many looks?#

Each look cuts the part still in play roughly in half, so the number of looks is about the number of times you can halve n before one item is left. That count is log n, the logarithm from the Big-O lesson, and it grows very slowly:

Going from a thousand items to a million makes the worst case of linear search a thousand times longer. Binary search needs 10 more looks.

Finding the middle safely#

Look closely at how the code finds the middle: it computes lo + (hi - lo) / 2. The obvious way is the average, (lo + hi) / 2, and for every array in this course the two give the same number. The difference is how big the numbers get along the way. An int holds whole numbers only up to 2,147,483,647. Add past that and the result wraps around to a large negative number, which is called overflow. Here are both formulas on two big indexes:

The average prints -397483648. lo + hi is 3.5 billion, too big for an int, so it wrapped around before the division ever happened. The safe version prints 1750000000, the true middle. It never adds the two indexes: it halves the distance between them and steps that far from lo, so every number along the way stays in range. (The _ marks in 1_500_000_000 only make the number easier to read. Java ignores them.)

Before moving on, rebuild binary search yourself.

Java's binary search: Arrays.binarySearch#

You will rarely need to write binary search, because java.util.Arrays already has one. Arrays.binarySearch(array, target)searches a sorted array and returns the target's index when it finds it. The interesting part is what comes back when the target is missing.

This prints 6, then -5, then 20 belongs at index 4. For 30, Java agrees with our method: index 6. For the missing 20, where our method would return -1, Java returns -5. That negative number carries extra information.

Reading a negative result#

When the target is missing, Java first works out the insertion point: the index where the target would go if you added it and kept the array sorted. That is the index of the first item bigger than the target, or the length of the array if every item is smaller. For 20, the first bigger item is 21, at index 4, so the insertion point is 4. Java then returns -(insertion point) - 1, which is -(4) - 1, or -5.

The extra minus one is there because an insertion point can be 0. If Java returned plain -(insertion point), a target that belongs at the very front would come back as 0, and 0already means “found at index 0”. Subtracting one more keeps every “missing” answer at -1 or below. So reading the result takes one check: 0 or more means found at that index, and anything negative means missing.

To get the insertion point back, undo the formula: -result - 1. The last lines of the program do that, which is useful when you want to add a value to sorted data and keep it sorted.

Sorting, and what stable means#

Binary search needs sorted data, so sorting comes next. People have invented dozens of sorting algorithms. This lesson traces three classics, each built on a different idea: selection sort, insertion sort and merge sort.

You have met one sort already: bubble sort, which keeps swapping side-by-side items that are out of order until none are left. It is the sort everybody hears about first. Donald Knuth, whose books are the standard reference on sorting, wrote that it has little going for it apart from its catchy name. Bubble sort is O(n²) and does more swapping than any sort in this lesson, so real code does not use it.

Stable and unstable sorts#

One more idea before the algorithms. Sometimes two items are equal by whatever you are sorting on. A sort that always keeps equal items in the order they started in is called stable. You met the word in Comparable, Comparator and sorting; here is what it looks like.

Picture a game's player list in alphabetical order: Ana, Ben, Cleo, Dev, Eli. You sort it by level, and Ana and Cleo are both on level 3. A stable sort keeps Ana in front of Cleo, so players on the same level stay alphabetical. An unstable sort is allowed to put Cleo first. With plain numbers you could never tell the difference, since one 3 looks exactly like another. With objects that carry more data, you can.

Selection sort: pick the smallest, again and again#

Suppose you are lining up friends by height. You scan the whole line, find the shortest person, and swap them into first place. Then you scan everyone except that first person, find the shortest of the rest, and swap them into second place. You keep going until you reach the end. That is selection sort: each pass selects the smallest item in the unsorted part of the array and swaps it to the front of that part.

As it runs, the array has two parts: a sorted part on the left that grows by one item each pass, and an unsorted part on the right that shrinks. Once an item joins the sorted part, it is in its final place and never moves again. Here are the passes on six heights:

The output shows the array after each pass, matching the table. In the trace, i marks the front of the unsorted part and j scans the rest of it. minIndex remembers where the smallest value so far sits, so it holds an index rather than a value. The three lines after the inner loop are the same swap you used in bubble sort. In passes 3 and 5 the smallest item is already at the front, so it swaps with itself and nothing changes.

How fast is selection sort?#

Count the comparisons for those six heights. The first pass compares 5 pairs, the next 4, then 3, 2 and 1, which is 15 in all. For n items it is n(n - 1) / 2, about half of n², so selection sort is O(n²). It makes exactly that many comparisons on every input, even one that is already sorted, because the only way to be sure which item is smallest is to look at all of them.

Its one strength is that it moves very little. Each pass ends in a single swap, so the whole sort makes only n - 1 swaps. That helps when writing to memory is slow, but it rarely matters in everyday code.

Is selection sort stable?#

No. Its long-distance swap can jump an item over an equal one. Here are three players sorted by level with exactly the selection sort above, now comparing levels.

It prints 1 Ben, 3 Cleo, 3 Ana. Ana starts in front of Cleo, and both are on level 3, yet Cleo comes out first. In the first pass the smallest level is Ben's, at the back. Swapping Ben to the front sends Ana to Ben's old place, behind Cleo, and nothing later moves her back. A stable sort would have kept Ana first.

Insertion sort: like sorting a hand of cards#

Think about how you sort playing cards as you pick them up one at a time. The cards already in your hand are in order. You take the next card, slide it left past every card bigger than it, and drop it into the gap. That is insertion sort: the left part of the array is a sorted hand, and each step inserts the next item into its place in that hand.

In code, sliding a card left takes a few lines. The new item waits in a variable called current. Every bigger item in the hand shifts one place to the right, which opens a gap. When the item on the left is not bigger, the gap is in the right spot, and current drops into it.

Watch j start just left of i and walk further left while it finds bigger cards, copying each of them one slot to the right. After the first shift the array briefly holds one value twice and seems to have lost the card you picked up. It has not: the card is safe in current, and the line after the loop writes it into the gap. The output shows the array after each card is placed, matching the table.

How fast is insertion sort?#

It depends on the input, which sets insertion sort apart from selection sort. On a backwards array every new card slides all the way to the front: 1 shift, then 2, then 3, up to n - 1, which adds up to about n² / 2. That is O(n²). On an array that is already sorted, each new card is compared once with the card to its left, found to be in place, and left alone: n - 1 comparisons and no shifts at all, which is O(n).

Real data is often nearly sorted, such as a list that was sorted yesterday and has had a few entries added since, and insertion sort gets through that kind of input in close to O(n) time. Its loop is also so simple that it beats cleverer sorts on small arrays. Those two strengths are why the sorts built into Java hand small pieces of work to insertion sort, as you will see at the end of this lesson.

Is insertion sort stable?#

Yes. A card only slides past cards that are strictly bigger, because the loop tests a[j] > current. It stops at an equal card, so equal items never pass each other. Change that > to >= and the array still ends up sorted, but equal items now hop over each other and the sort is no longer stable.

1import java.util.Arrays;
2 
3public class Main {
4    public static void main(String[] args) {
5        check("mixed", new String[] {"Paris", "Cairo", "Lima", "Oslo", "Delhi"});
6        check("one city", new String[] {"Rome"});
7        check("empty", new String[] {});
8        check("backwards", new String[] {"Tokyo", "Seoul", "Quito", "Nairobi", "Accra"});
9        check("repeats", new String[] {"Lima", "Doha", "Lima", "Baku", "Doha"});
10    }
11 
12    static void check(String label, String[] cities) {
13        insertionSort(cities);
14        System.out.println(label + ": " + Arrays.toString(cities));
15    }
16 
17    static void insertionSort(String[] words) {
18        // TODO: put words into alphabetical order with insertion sort.
19    }
20}

Merge sort: divide and conquer#

Selection sort and insertion sort both inch through the array one item at a time, and both are O(n²) in the worst case. Merge sort reaches O(n log n) with a different plan, called divide and conquer: split a problem into smaller copies of itself, solve the copies, then combine their answers. If that sounds like recursion, it is. Merge sort is a recursive method, and its plan has four steps:

1. 1If the array has 0 or 1 items, it is already sorted, so stop. This is the base case.
2. 2Otherwise, split it into a left half and a right half.
3. 3Sort each half by calling merge sort on it.
4. 4Merge the two sorted halves into one sorted array.

Step 3 can look like cheating: to sort an array, you sort its halves. It works for the reason all recursion works. Each call gets a smaller array, the splitting ends at arrays of one item, and those are sorted already. Every comparison between items happens in step 4. Here is the whole process on eight numbers:

The merge step#

Merging is easiest to picture with two piles of cards, each sorted with the smallest on top. Compare the two top cards, take the smaller one, and add it to a new pile. Repeat. When one pile runs out, move the rest of the other pile across in one go. Every comparison places one card, so merging piles with n cards between them takes at most n - 1 comparisons.

This merges the last two piles from the table and prints [7, 15, 19, 23, 36, 44, 52, 61]. In the trace, i is the top of the left pile, j the top of the right pile, and k the next free slot in result. The first loop runs while both piles have cards. The last two loops copy whatever is left, and only one of them ever runs, because by then one pile is empty.

Look at the test in the first loop: left[i] <= right[j]. On a tie it takes from the left pile. Every item in the left half started out in front of every item in the right half, so taking the left one first keeps equal items in their original order. That is what makes merge sort stable. With < instead, a tie would take from the right pile and swap the two equal items.

The whole sort#

Now the recursive method, following the four steps. It splits with Arrays.copyOfRange(a, from, to), which copies the items from index from up to, but not including, index to into a new array. The merge also prints each merge it makes, so the output is a log of the work.

The merges come out in a different order from the table. The table works level by level, but the program finishes the whole left half, splitting all the way down and merging all the way back up, before it touches the right half. Step through it with the call stack in view: it grows as the calls split the array and shrinks as each merge returns. The last line printed is the sorted array, [7, 15, 19, 23, 36, 44, 52, 61].

How fast is merge sort?#

Look at the table again. Each round of merging handles every item once, so one round costs about n steps. The number of rounds is the number of times n can be halved before the pieces have one item each, which is log n. Multiply the two and merge sort is O(n log n), on every input, sorted or not.

The gap from O(n²) is huge once n is large. To sort a million items, selection sort makes about 500 billion comparisons. Merge sort needs fewer than 20 million.

The price is memory. Selection sort and insertion sort rearrange the array they are given and need only a few extra variables, which is O(1) extra space. Merge sort copies items into new arrays as it works, so it needs extra space that grows with n: O(n).

Key idea

Divide and conquer: split the problem in half, solve each half the same way, and combine the answers. Merge sort splits log n times and does about n steps of merging per level, which makes it O(n log n).

The three sorts side by side#

Here are all three on the same twelve bars. Choose a sort, press Play or step one move at a time, and watch the two counters. A comparison is one “which is smaller?” question, and a move is one value written into a slot.

Run each sort on the same numbers, then press New numbers and run them again. Selection sort makes 66 comparisons every time, which is 12 × 11 / 2. Insertion sort's count changes with the numbers. Merge sort never needs more than 33.

What Java does when you call sort#

In real programs you sort with one line. Arrays.sort sorts an array in place. List.sort sorts a list, and Collections.sort(list) is an older way to call the same thing.

This prints [54, 61, 72, 79, 88, 95], then [Adam, Leo, Mia, Zara], then [19, 19, 25, 31]. Each comes out in its natural order: numbers from smallest to largest, and strings alphabetically.

Two algorithms behind one name#

The calls look alike, but Java picks a different algorithm depending on what you are sorting. Both arrived in Java 7.

• For arrays of primitives such as int[] and double[], Arrays.sort uses dual-pivot quicksort, by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch. Quicksort is another divide and conquer sort. It picks an item called a pivot, splits the array into the items smaller than the pivot and the items bigger, then sorts each part. The dual-pivot version picks two pivots and splits into three parts. Java's version promises O(n log n) on every input: if the splits keep coming out lopsided, it switches to another algorithm, heapsort, to keep that promise.
• For arrays of objects such as String[], and for List.sort and Collections.sort, Java uses TimSort, adapted from the sort Tim Peters wrote for Python. It is a merge sort at heart, so it is O(n log n) and stable, and it is tuned for real data. It looks for runs that are already in order, forwards or backwards, and merges those, so on a nearly sorted list it needs only about n comparisons.

Both switch to insertion sort for small pieces of a few dozen items, because its simple loop beats the heavier machinery when there is little to do. TimSort uses a version called binary insertion sort, which finds each item's place with a binary search.

Why objects get a stable sort#

A sort of primitives has no need to be stable: two equal ints are the same number, and nobody can tell which 3 came first. Objects carry other data, so the order of equal objects shows, and every object sort in Java guarantees stability. Here is the player list again, sorted by level with List.sort and a comparator.

The output is 1 Ben, 1 Eli, 2 Dev, 3 Ana, 3 Cleo. Ben and Eli share level 1 and keep their original order, and so do Ana and Cleo on level 3. The selection sort earlier flipped Ana and Cleo; List.sort never will.

Why you almost always call the library#

So the advice for real code is simple: call Arrays.sort or List.sort, and search sorted arrays with Arrays.binarySearch. The library sorts are faster than anything you would write in an afternoon, they take advantage of data that is partly sorted already, the object sort is guaranteed stable, and they have been tested on far more inputs than any course exercise. A sort of your own is one more place for a bug like the midpoint overflow to hide.

Writing the classics yourself is still worth doing once. It is how you learn what O(n log n) buys and what a stable sort promises, and writing binary search or merge sort from memory is a popular job interview question.

Key idea

In real code, sort with Arrays.sort or List.sort and search with Arrays.binarySearch. Writing your own sort is how you learn what those calls do for you.

Further reading#

• The java.util.Arrays reference for Java 25, including the notes on how sort and binarySearch work
• List.sort in the Java 25 API, with its promise to keep equal elements in order
• Collections.binarySearch, the version for lists, and what it does with lists that are slow to index