Searching and sorting: linear, binary, selection, insertion, merge sort

Searching and sorting are the first stop of algorithm analysis. This week you trace two search and three sorting algorithms step by step. Typical exam questions: “what does the array look like after the second pass when selection sort is applied to this array”, “which indexes does binary search look at”, and “what is its Big-O, and why”. Instead of memorizing the code, know the one-sentence idea of each algorithm; the code follows from that idea.

Golden rules:

1. Binary search works only on a sorted array. It halves the range at each step.
2. Selection sort: find the smallest of the rest and put it at the front.
3. Insertion sort: shift the next element into its place in the sorted part on the left.
4. Merge sort: split in two, sort the two halves, merge.
5. Big-O: linear $O(n)$, binary $O(\log n)$, selection and insertion $O(n^2)$, merge $O(n \log n)$.

Searching

Linear search

Walk through the array one by one from the start, and return the index when you see the searched value. The array does not have to be sorted.

static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == key) return i;
    return -1;
}
int[] data = {42, 7, 19, 3, 25, 7};

Three searches, also counting the comparisons:

1 comps=2
4 comps=5
-1 comps=6

(When 7 is searched, the first 7 is found, index 1; 5 comparisons for 25; 99 is not there, the whole array was looked at.)

Binary search

If the array is sorted, look at the middle element. If the searched value is larger, you can eliminate the left half entirely; if smaller, the right half. Last week we wrote it recursively; the loop version:

static int binarySearch(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;    // right half
        else high = mid - 1;                // left half
    }
    return -1;
}
int[] sorted = {2, 5, 9, 14, 20, 27, 33, 41, 48, 56, 63};
binarySearch(sorted, 41);
binarySearch(sorted, 4);

  low=0 high=10 mid=5 a[mid]=27
  low=6 high=10 mid=8 a[mid]=48
  low=6 high=7 mid=6 a[mid]=33
  low=7 high=7 mid=7 a[mid]=41
index 7 comps=4
  low=0 high=10 mid=5 a[mid]=27
  low=0 high=4 mid=2 a[mid]=9
  low=0 high=1 mid=0 a[mid]=2
  low=1 high=1 mid=1 a[mid]=5
index -1 comps=4

When 4 is searched, at the last step low = 1, high = 1, and since a[1] = 5 > 4, high = 0; low > high and the loop ends: −1.

PITFALL · low < high. If you write the condition with <, when the range shrinks to a single element that element is never checked. On the array {2, 5, 9} this faulty version found 5 but returned −1 for 9 and 2.

Java’s built-in version: Arrays.binarySearch(sorted, 27) → 5. It also expects the array to be sorted; if it is not sorted, the result is meaningless.

Sorting

We will trace the three algorithms on the same array: {29, 10, 14, 37, 13}.

Selection sort

The idea: find the smallest element in the unsorted part of the array and swap it with the start of that part. In each pass, one more element from the front settles into its final place.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        int tmp = a[i]; a[i] = a[min]; a[min] = tmp;   // swap
    }
}

The array after each pass:

  pass 1: [10, 29, 14, 37, 13]
  pass 2: [10, 13, 14, 37, 29]
  pass 3: [10, 13, 14, 37, 29]
  pass 4: [10, 13, 14, 29, 37]
comps=10

pass 1: [29 10 14 37 13]  smallest 10 (index 1) ↔ index 0    → [10 | 29 14 37 13]
pass 2: [10 | 29 14 37 13] smallest 13 (index 4) ↔ index 1   → [10 13 | 14 37 29]
pass 3: smallest 14 is already at index 2                    → [10 13 14 | 37 29]
pass 4: smallest 29 (index 4) ↔ index 3                      → [10 13 14 29 | 37]

The number of comparisons is the same for every input: $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$. For n = 5 it is 10. That is why selection sort is $O(n^2)$ in every case.

Insertion sort

The idea: like sorting cards in your hand. The part on the left is always sorted. Take the next element (key), shift the ones larger than it one place to the right, and put the key in the gap that opens.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];     // shift right
            j--;
        }
        a[j + 1] = key;
    }
}

  pass 1: [10, 29, 14, 37, 13]
  pass 2: [10, 14, 29, 37, 13]
  pass 3: [10, 14, 29, 37, 13]
  pass 4: [10, 13, 14, 29, 37]
comps=8

Compare the passes of the two algorithms: in selection sort the elements at the front are final (after pass 2, 10 and 13 never change again). In insertion sort the front part is sorted but not final: in pass 3, [10, 14, 29, 37] is sorted but 13 slipped in between later.

Insertion sort’s comparison count depends on the input:

On sorted input, insertion sort makes one comparison per element and stops: the best case is $O(n)$. On reverse-ordered input each element slides all the way to the front: the worst case is $O(n^2)$.

Merge sort

The idea: divide and conquer. Split the array in two, sort the two halves recursively, then merge the two sorted halves into a single sorted array (merge). An array with one element is already sorted: the base case.

static void mergeSort(int[] a, int low, int high) {
    if (low >= high) return;                 // 0 or 1 elements
    int mid = (low + high) / 2;
    mergeSort(a, low, mid);                  // left half
    mergeSort(a, mid + 1, high);             // right half
    merge(a, low, mid, high);                // merge
}
static void merge(int[] a, int low, int mid, int high) {
    int[] tmp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // take the smaller one
    while (i <= mid) tmp[k++] = a[i++];                // the leftovers
    while (j <= high) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, low, tmp.length);
}

For {38, 27, 43, 3, 9, 82, 10}, the state of that range after each merge:

  merge [0..1]: [27, 38]
  merge [2..3]: [3, 43]
  merge [0..3]: [3, 27, 38, 43]
  merge [4..5]: [9, 82]
  merge [4..6]: [9, 10, 82]
  merge [0..6]: [3, 9, 10, 27, 38, 43, 82]
[3, 9, 10, 27, 38, 43, 82] comps=14

                 [38 27 43 3 9 82 10]
            [38 27 43 3]          [9 82 10]
         [38 27]   [43 3]       [9 82]   [10]
        [38] [27] [43] [3]     [9] [82]
         └─┬─┘     └─┬─┘        └─┬─┘
        [27 38]   [3 43]       [9 82]
           └────┬────┘            └──┬──┘
        [3 27 38 43]            [9 10 82]
                └──────────┬──────────┘
              [3 9 10 27 38 43 82]

The splitting takes $\log_2 n$ levels, and at each level a total of n elements are merged: $O(n \log n)$, independent of the input. The cost: extra $O(n)$ memory for the temporary array.

Big-O comparison

The practical counterpart of the theory: comparisons counted on reverse-ordered arrays.

When n doubles, selection sort’s work quadruples ($n^2$), while merge sort’s grows a little more than double ($n \log n$).

TIP · in real life. You do not write your own sort: Arrays.sort(array) and Collections.sort(list) are ready and $O(n \log n)$. In the exam, however, you are asked to trace and write the algorithm by hand; the built-in method is not accepted.

Common mistakes

int[] a = {29, 10, 14, 37, 13};

int[] a = {29, 10, 14, 37, 13};

static int search(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

public static void sortByLength(String[] words) {
    for (int i = 1; i < words.length; i++) {
        String key = words[i];
        int j = i - 1;
        while (j >= 0 && words[j].length() > key.length()) {
            words[j + 1] = words[j];   // shift right
            j--;
        }
        words[j + 1] = key;
    }
}