Sorting Algorithms

A music app shows your songs from most played to least played. A teacher’s gradebook lists students alphabetically. A race posts finishing times from fastest to slowest. In each case, someone had a jumbled collection and put it in order. Programs do this constantly, because ordered data is far easier for people to read and for other algorithms to use.

A collection is sorted when its elements are arranged in order according to some rule. In ascending order, each element is less than or equal to the one after it (smallest first): 3 7 7 12 20. In descending order, each element is greater than or equal to the one after it (largest first): 20 12 7 7 3. Notice “or equal to”: repeated values are allowed, and they simply sit next to each other. Unless a question says otherwise, “sorted” in this chapter means ascending.

That definition only talks about neighbors. To check whether an array is in ascending order, you do not have to compare every element with every other element. You only need to check that no element is bigger than the one right after it. If every neighboring pair is in order, the whole array is in order.

int[] scores = {12, 18, 18, 25, 31};
boolean sorted = true;
for (int i = 0; i < scores.length - 1; i++)
{
    if (scores[i] > scores[i + 1])
    {
        sorted = false;
    }
}
System.out.println("scores sorted? " + sorted);

int[] times = {40, 35, 52, 61};
boolean timesSorted = true;
for (int i = 0; i < times.length - 1; i++)
{
    if (times[i] > times[i + 1])
    {
        timesSorted = false;
    }
}
System.out.println("times sorted? " + timesSorted);

scores sorted? true
times sorted? false

A sorting algorithm is a step-by-step process that rearranges the elements of a collection into sorted order. This chapter teaches two of them: selection sort and insertion sort. Both are iterative: they repeat their steps with loops. Both work on an array or an ArrayList.

Both algorithms share one big idea. At any moment during the sort, the list is split into two parts. The sorted portion at the front is already in order. The unsorted portion after it has not been dealt with yet. Each pass of the algorithm moves one more element into the sorted portion, so the sorted portion grows by one and the unsorted portion shrinks by one, until the unsorted portion is empty. The two algorithms differ in how they choose the next element and where they put it.

sorted portion | unsorted portion
    7  12      |  45  29  18

int[] scores = {12, 18, 18, 25, 31};
boolean sorted = true;
for (int i = 0; i < scores.length; i++)
{
    if (scores[i] > scores[i + 1])
    {
        sorted = false;
    }
}
System.out.println("scores sorted? " + sorted);

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

int[] heights = {4, 9, 6, 8, 2};
int outOfOrder = 0;
for (int i = 0; i < heights.length - 1; i++)
{
    if (heights[i] > heights[i + 1])
    {
        outOfOrder++;
    }
}
System.out.println(outOfOrder);

2

Imagine five numbered cards face up on a table, in a jumbled row. One natural way to put them in order: find the smallest card and move it to the far left. Then find the smallest of the cards that are left and put it second. Keep going. That is selection sort. Before writing any code, you need to be able to do it by hand, because that is exactly what AP questions ask: “What does the array look like after two passes?”

In Topic 4.5 you found the smallest value in an array with a traversal. Selection sort runs that same search over and over, each time on a smaller part of the array.

Here is the algorithm in plain steps. Each repetition is called a pass.

1. Look at the unsorted portion and find its smallest element.
2. Swap that element with the first element of the unsorted portion.
3. The sorted portion now has one more element. Repeat on what is left.

Selection sort gets its name from step 1: each pass selects the smallest remaining element. The element it places is in its final position: since it is the smallest of everything left, nothing that comes later can belong in front of it. It will never move again.

Selection sort uses a swap, not a shift. Only two elements change places in a pass. The element that was sitting in the first unsorted spot jumps to wherever the smallest element came from.

Selection sort works just as well by selecting the largest element instead. Choosing the largest each pass and swapping it to the front sorts into descending order. Here it is by hand on 14 30 9 30 22:

Two things changed from the first example: the rule (largest instead of smallest) and the data (it has a repeated value). The structure is identical: find, swap, grow the sorted portion by one. In pass 1, two elements tie for largest. Taking the first one found works fine; the second 30 is placed on the very next pass. (You could also select the largest each pass and swap it to the end of the array; that builds an ascending list from the back.)

Doing selection sort by hand, you saw the smallest element right away. Java cannot glance at an array; it has to scan element by element, exactly like the find-the-minimum traversal from Topic 4.5. So the code is a loop (one pass per repetition) with a find-the-minimum loop nested inside it, which is the nested loop shape from Topic 2.11.

Here is selection sort as a static method (Topic 3.5), with a println at the end of each pass so you can watch it work. The printArray helper just prints the elements on one line, separated by spaces.

public class SelectionSort
{
    public static void selectionSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            System.out.print("After pass " + (i + 1) + ": ");
            printArray(arr);
        }
    }

    public static void printArray(int[] arr)
    {
        System.out.print(arr[0]);
        for (int k = 1; k < arr.length; k++)
        {
            System.out.print(" " + arr[k]);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] scores = {29, 12, 45, 7, 18};
        System.out.print("Start:        ");
        printArray(scores);
        selectionSort(scores);
    }
}

Start:        29 12 45 7 18
After pass 1: 7 12 45 29 18
After pass 2: 7 12 45 29 18
After pass 3: 7 12 18 29 45
After pass 4: 7 12 18 29 45

To select the largest element instead, only the comparison changes: arr[j] > arr[maxIndex] keeps the position of the biggest value seen so far. (The variable is renamed maxIndex so the name says what it holds.) This program runs the descending sort you traced by hand in 4.15.2:

public class SelectionDescending
{
    public static void sortHighToLow(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int maxIndex = i;
            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] > arr[maxIndex])
                {
                    maxIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
            System.out.print("After pass " + (i + 1) + ": ");
            printArray(arr);
        }
    }

    public static void printArray(int[] arr)
    {
        System.out.print(arr[0]);
        for (int k = 1; k < arr.length; k++)
        {
            System.out.print(" " + arr[k]);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] points = {14, 30, 9, 30, 22};
        System.out.print("Start:        ");
        printArray(points);
        sortHighToLow(points);
    }
}

Start:        14 30 9 30 22
After pass 1: 30 14 9 30 22
After pass 2: 30 30 9 14 22
After pass 3: 30 30 22 14 9
After pass 4: 30 30 22 14 9

One character in the comparison decides the order. Everything else, the passes, the inner search, and the swap, is the same.

public class SwapNoTemp
{
    public static void selectionSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            arr[i] = arr[minIndex];
            arr[minIndex] = arr[i];
        }
    }

    public static void printArray(int[] arr)
    {
        System.out.print(arr[0]);
        for (int k = 1; k < arr.length; k++)
        {
            System.out.print(" " + arr[k]);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] scores = {29, 12, 45, 7, 18};
        selectionSort(scores);
        printArray(scores);
    }
}

7 7 7 7 18

int[] arr = {29, 12, 45, 7, 18};
int i = 0;
int minIndex = i;
int updates = 0;
for (int j = i + 1; j < arr.length; j++)
{
    if (arr[j] < arr[minIndex])
    {
        minIndex = j;
        updates++;
    }
}
System.out.println("minIndex updated " + updates + " times; minIndex is " + minIndex);

minIndex updated 2 times; minIndex is 3

Think about how many people sort a hand of playing cards. They pick up cards one at a time. Each new card gets slid into the right spot among the cards already in their hand, so the hand stays in order the whole time. They never search the rest of the deck for the smallest card. That is insertion sort.

Like selection sort, insertion sort keeps a sorted portion at the front. The difference is where the next element comes from. Insertion sort does not hunt for the smallest remaining element. It simply takes the next element, the first one in the unsorted portion, and inserts it into the right place among the sorted elements.

To make room, the larger sorted elements shift one position to the right. This is the shift from Topic 4.5: each element moves over one spot, and the element being inserted drops into the gap.

1. At the start, the first element alone counts as the sorted portion (one element is always in order).
2. Take the first element of the unsorted portion. Call it the current element.
3. Moving left through the sorted portion, shift every element that is larger than the current element one place right.
4. Put the current element into the gap. The sorted portion has grown by one. Repeat.

Here is the key difference from selection sort: the element insertion sort places is in its correct position within the sorted portion, but not necessarily its final position. A smaller value that has not been looked at yet may come along later and push it further right.

Now zoom in on pass 3 to see the shifting one step at a time. Before the pass, the array is 12 29 45 7 18, and 7 is the current element. Java cannot shift everything at once; each step copies one element one place to the right:

start:           12 29 45  7 18    current = 7 (saved)
shift 45 right:  12 29 45 45 18
shift 29 right:  12 29 29 45 18
shift 12 right:  12 12 29 45 18
insert 7:         7 12 29 45 18

In the middle steps, one value appears twice. That is expected: shifting copies a value into the next spot, and the old copy is overwritten on the following step (or by the inserted element at the end). The 7 is not lost because it was saved before the shifting started; its spot at index 3 is the first one overwritten. You will see why that saving step matters in the code.

By hand, you could see where the current element belonged and slide everything over at once. Java has to work its way left through the sorted portion one element at a time, deciding at each step whether to shift or stop. Because the number of shifts is not known in advance (zero in pass 2, three in pass 3), the inner loop is a while loop from Topic 2.7 rather than a counting for loop.

public class InsertionSort
{
    public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
            System.out.print("After pass " + i + ": ");
            printArray(arr);
        }
    }

    public static void printArray(int[] arr)
    {
        System.out.print(arr[0]);
        for (int k = 1; k < arr.length; k++)
        {
            System.out.print(" " + arr[k]);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] scores = {29, 12, 45, 7, 18};
        System.out.print("Start:        ");
        printArray(scores);
        insertionSort(scores);
    }
}

Start:        29 12 45 7 18
After pass 1: 12 29 45 7 18
After pass 2: 12 29 45 7 18
After pass 3: 7 12 29 45 18
After pass 4: 7 12 18 29 45

The loop on line 9 can stop for two different reasons. Compare pass 3 and pass 4.

Pass 3 (i is 3, current is 7, array 12 29 45 7 18):

Pass 4 (i is 4, current is 18, array 7 12 29 45 18):

In pass 3, the current element was smaller than everything, so the loop ran off the left end: j reached −1 and j >= 0 stopped it. In pass 4, the loop found a smaller element (12) and stopped there. Notice “not checked” in the last row of pass 3. Because && short-circuits (Topic 2.5), when j >= 0 is false, Java never evaluates arr[-1] > current. That is what keeps the code safe.

public class InsertionAndOrder
{
    public static void main(String[] args)
    {
        int[] scores = {29, 12, 45, 7, 18};
        for (int i = 1; i < scores.length; i++)
        {
            int current = scores[i];
            int j = i - 1;
            while (scores[j] > current && j >= 0)
            {
                scores[j + 1] = scores[j];
                j--;
            }
            scores[j + 1] = current;
        }
        System.out.println("Sorted!");
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
	at InsertionAndOrder.main(InsertionAndOrder.java:10)

public class InsertionLostValue
{
    public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[i])
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = arr[i];
        }
    }

    public static void main(String[] args)
    {
        int[] scores = {29, 12, 45, 7, 18};
        insertionSort(scores);
        for (int value : scores)
        {
            System.out.println(value);
        }
    }
}

int current = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > current)
{
    arr[j + 1] = arr[j];
    j--;
}
arr[j + 1] = current;

Both algorithms work on an ArrayList as well as an array, and the steps are exactly the same. Only the syntax for reading and writing elements changes, as you saw when you moved array algorithms over to ArrayList in Topic 4.10:

Sorting an ArrayList uses set to put values into positions that already exist. It does not use add or remove, because the list never changes size: elements only trade or shift places.

A second change comes from the element type. An ArrayList<Integer> holds Integer objects, but list.get(j) < list.get(minIndex) still works because each Integer unboxes to an int before comparing (Topic 4.7). An ArrayList<String> is different: < and > do not work on String objects at all. To compare strings in dictionary order, use compareTo from Topic 1.15. The test “a comes after b” is written a.compareTo(b) > 0.

import java.util.ArrayList;

public class SortArrayList
{
    public static void selectionSort(ArrayList<Integer> list)
    {
        for (int i = 0; i < list.size() - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < list.size(); j++)
            {
                if (list.get(j) < list.get(minIndex))
                {
                    minIndex = j;
                }
            }
            int temp = list.get(i);
            list.set(i, list.get(minIndex));
            list.set(minIndex, temp);
        }
    }

    public static void insertionSort(ArrayList<String> list)
    {
        for (int i = 1; i < list.size(); i++)
        {
            String current = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j).compareTo(current) > 0)
            {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, current);
            System.out.println("After pass " + i + ": " + list);
        }
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> laps = new ArrayList<Integer>();
        laps.add(62);
        laps.add(58);
        laps.add(71);
        laps.add(55);
        selectionSort(laps);
        System.out.println("Laps: " + laps);

        ArrayList<String> names = new ArrayList<String>();
        names.add("Mia");
        names.add("Ava");
        names.add("Zoe");
        names.add("Eli");
        insertionSort(names);
    }
}

Laps: [55, 58, 62, 71]
After pass 1: [Ava, Mia, Zoe, Eli]
After pass 2: [Ava, Mia, Zoe, Eli]
After pass 3: [Ava, Eli, Mia, Zoe]

import java.util.ArrayList;

public class StringLessThan
{
    public static void insertionSort(ArrayList<String> list)
    {
        for (int i = 1; i < list.size(); i++)
        {
            String current = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j) > current)
            {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, current);
        }
    }
}

StringLessThan.java:11: error: bad operand types for binary operator '>'
            while (j >= 0 && list.get(j) > current)
                                         ^
  first type:  String
  second type: String

You now know two algorithms that end with the same sorted list. A common exam question shows a list partway through a sort and asks which algorithm produced it. Another asks which one does more work. Both questions come down to what each pass does.

The fourth row is the fastest way to identify a sort. After pass k of selection sort, the front holds the smallest values in the whole list. After pass k of insertion sort, the front holds whatever values started in the first k + 1 positions, now in order, and the rest of the list is untouched.

The program below counts the main work of each sort on three 5-element arrays: how many times selection sort compares two elements (the if inside its inner loop), and how many times insertion sort shifts an element (the body of its while loop). Each sort gets its own copy of the data, because sorting changes the array.

public class CountWork
{
    public static int selectionComparisons(int[] arr)
    {
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++)
            {
                count++;
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return count;
    }

    public static int insertionShifts(int[] arr)
    {
        int count = 0;
        for (int i = 1; i < arr.length; i++)
        {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current)
            {
                count++;
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
        return count;
    }

    public static void report(String label, int[] forSelection, int[] forInsertion)
    {
        System.out.println(label + " selection comparisons " + selectionComparisons(forSelection)
            + ", insertion shifts " + insertionShifts(forInsertion));
    }

    public static void main(String[] args)
    {
        int[] mixedA = {29, 12, 45, 7, 18};
        int[] mixedB = {29, 12, 45, 7, 18};
        int[] sortedA = {7, 12, 18, 29, 45};
        int[] sortedB = {7, 12, 18, 29, 45};
        int[] reverseA = {45, 29, 18, 12, 7};
        int[] reverseB = {45, 29, 18, 12, 7};
        report("Mixed:  ", mixedA, mixedB);
        report("Sorted: ", sortedA, sortedB);
        report("Reverse:", reverseA, reverseB);
    }
}

Mixed:   selection comparisons 10, insertion shifts 6
Sorted:  selection comparisons 10, insertion shifts 0
Reverse: selection comparisons 10, insertion shifts 10

Selection sort makes 10 comparisons no matter what: its inner loop runs 4 + 3 + 2 + 1 = 10 times, the shrinking nested loop you counted in Topic 2.12. Even on an array that is already sorted, it still has to scan to prove each element is the smallest. Insertion sort’s work changes with the data. On the sorted array, every current element is already larger than its left neighbor, so the while condition is false right away and nothing shifts. On the reversed array, every element must shift all the way to the front: 1 + 2 + 3 + 4 = 10 shifts. The mixed array falls in between: 1 + 0 + 3 + 2 = 6.

A race organizer has five finishing times in seconds, including a tie, and wants them in order so the top three can be announced. This program sorts one copy with selection sort and another with insertion sort, printing every pass, then reads the top three from the sorted array. Predict both sets of states before reading the output.

public class RaceResults
{
    public static void selectionSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            System.out.print("  pass " + (i + 1) + ": ");
            printArray(arr);
        }
    }

    public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
            System.out.print("  pass " + i + ": ");
            printArray(arr);
        }
    }

    public static void printArray(int[] arr)
    {
        System.out.print(arr[0]);
        for (int k = 1; k < arr.length; k++)
        {
            System.out.print(" " + arr[k]);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int[] timesA = {61, 48, 55, 48, 52};
        int[] timesB = {61, 48, 55, 48, 52};
        System.out.println("Selection sort:");
        selectionSort(timesA);
        System.out.println("Insertion sort:");
        insertionSort(timesB);
        System.out.println("Top three times: " + timesB[0] + ", " + timesB[1] + ", " + timesB[2]);
    }
}

Selection sort:
  pass 1: 48 61 55 48 52
  pass 2: 48 48 55 61 52
  pass 3: 48 48 52 61 55
  pass 4: 48 48 52 55 61
Insertion sort:
  pass 1: 48 61 55 48 52
  pass 2: 48 55 61 48 52
  pass 3: 48 48 55 61 52
  pass 4: 48 48 52 55 61
Top three times: 48, 48, 52

• A list is sorted in ascending order when every element is less than or equal to the one after it; checking each neighboring pair is enough to tell.
• Selection sort and insertion sort are iterative sorts for arrays and ArrayLists. Both grow a sorted portion at the front by one element per pass, so n elements take n − 1 passes.
• Selection sort scans the unsorted portion for the smallest (or largest) element and swaps it into the first unsorted position, which is its final position. Its code is a find-the-minimum loop inside a pass loop, followed by a three-step swap.
• Insertion sort saves the next unsorted element, shifts larger sorted elements one place right, and drops the saved element into the gap. Its place is correct among the sorted elements but not necessarily final. The while condition must check j >= 0 before arr[j].
• On an ArrayList, use get, set, and size; compare String values with compareTo. To tell the sorts apart, check whether the front holds the smallest values overall (selection) or the original front values in order (insertion). Selection sort’s comparisons never change with the data; insertion sort’s shifts do.

import java.util.ArrayList;

public class SelectionWords
{
    public static void main(String[] args)
    {
        ArrayList<String> fruits = new ArrayList<String>();
        fruits.add("pear");
        fruits.add("fig");
        fruits.add("kiwi");
        fruits.add("apple");
        fruits.add("date");
        for (int i = 0; i < fruits.size() - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < fruits.size(); j++)
            {
                if (fruits.get(j).compareTo(fruits.get(minIndex)) < 0)
                {
                    minIndex = j;
                }
            }
            String temp = fruits.get(i);
            fruits.set(i, fruits.get(minIndex));
            fruits.set(minIndex, temp);
            System.out.println(fruits);
        }
    }
}

[apple, fig, kiwi, pear, date]
[apple, date, kiwi, pear, fig]
[apple, date, fig, pear, kiwi]
[apple, date, fig, kiwi, pear]

public class MinIndexBug
{
    public static void main(String[] args)
    {
        int[] arr = {29, 12, 45, 7, 18};
        int minIndex = 0;
        for (int i = 0; i < arr.length - 1; i++)
        {
            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        for (int value : arr)
        {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

for (int i = 0; i < arr.length - 1; i++)
{
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++)

int[] arr = {3, 1, 4, 2};
int shifts = 0;
for (int i = 1; i < arr.length; i++)
{
    int current = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > current)
    {
        arr[j + 1] = arr[j];
        shifts++;
        j--;
    }
    arr[j + 1] = current;
}
System.out.println(shifts);

int[] arr = {9, 4, 7, 1, 5};
for (int i = 1; i < 3; i++)
{
    int current = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > current)
    {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = current;
}
for (int value : arr)
{
    System.out.print(value + " ");
}
System.out.println();

4 7 9 1 5

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can explain what ascending order means and check whether an array is sorted by comparing neighbors. Reread
• I can carry out selection sort by hand and write the list after each pass. Reread
• I can trace the selection sort code, including how minIndex changes and how the swap works. Reread
• I can carry out insertion sort by hand and show which elements shift on each pass. Reread
• I can trace the insertion sort code and explain why j >= 0 must come first in the while condition. Reread
• I can follow both sorts on an ArrayList, including comparing String values with compareTo. Reread
• I can tell which sort produced a given in-between state and compare how much work each sort does. Reread