Algorithms 101: Sorting

This article will cover several sorting algorithms: working in quadratic time (bubble, insertion and selection sort), in loglinear time (merge sort, quicksort and heap sort) and in linear time, but only for special data types (counting and radix sort). Source code of examples used in this article is available in git repo.

Quadratic time algorithms

There is not much to say about quadratic time algorithms. Usually, they are not used by their own, but with some loglinear algorithm instead. For example, insertion sort sometimes is used inside merge sort or quicksort to sort small subarrays. As for bubble sort, usually it is considerably slower that other quadratic time sort algorithms and not used in practice.

Bubble sort

Idea: repeatedly iterate over an array comparing items pairwise and exchanging if they are out of order. It is easy to notice that on each step the biggest item will be placed at the end of an array, thus at most n iterations is needed to put all items in their places. This algorithm is stable.

package com.dancingrobot84.algorithms.sorting;

import com.dancingrobot84.algorithms.util.ArraysExt;

public class BubbleSort {
    public static void sort(int[] array) {
        boolean isSorted;
        do {
            isSorted = true;
            for (int i = 0; i < array.length - 1; i++) {
                if (array[i] > array[i+1]) {
                    ArraysExt.swap(array, i, i+1);
                    isSorted = false;
                }
            }
        } while (!isSorted);
    }
}

Insertion sort

Idea: iterate over an array keeping its left side sorted. When next item is encountered, push it further to the left until it is less or equal than other items. There are two loops, each of at most n iterations, thus quadratic time. This algorithm is stable.

package com.dancingrobot84.algorithms.sorting;

import com.dancingrobot84.algorithms.util.ArraysExt;

public class InsertionSort {
    public static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0 && array[j] < array[j-1]; j--) {
                ArraysExt.swap(array, j, j-1);
            }
        }
    }
}

Selection sort

Idea: iterate over all positions in array. For each position i search for minimal item in the range of [i, n] and put it in position i. For each iteration searching for minimal item will take O(n) time, thus giving quadratic time overall. This algorithm can be implemented as stable, however, the implementation below is not stable.

package com.dancingrobot84.algorithms.sorting;

import com.dancingrobot84.algorithms.util.ArraysExt;

public class SelectionSort {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int curMinIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[curMinIndex]) {
                    curMinIndex = j;
                }
            }
            ArraysExt.swap(array, curMinIndex, i);
        }
    }
}

Loglinear time algorithms

Loglinear algorithms are the ones that widely used in practice. It is proven that it is not possible to sort arbitrary data using comparisons faster than in O(nlog(n)) time, so these algorithms are the fastest ones. However, which algorithm to use in a program depends on its goals and constraints.

Merge sort

Idea: (top-down merge sort) split array in halves, sort each half recursively and then merge them. Using master theorem, T(n) = 2T(n/2) + O(n) = O(nlog(n)). This algorithm is stable.

Bottom-up merge sort treats n-element array as n singleton arrays. It merges them pairwise producing n/2 two-element arrays, merging them again and again until it merges two n/2-element arrays into one. It can be implemented without recursion.

The implementation below use O(n) space for buffer array which is used for merging two subarrays. This is standard recursive top-down merge sort.

package com.dancingrobot84.algorithms.sorting;

import java.util.Arrays;

public class MergeSort {
    public static void sort(int[] array) {
        new Sorter(array).sort();
    }

    private static class Sorter {

        private final int[] originalArray;
        private final int[] buffer;

        public Sorter(int[] array) {
            originalArray = array;
            buffer = new int[array.length];
        }

        public void sort() {
            sort(0, originalArray.length-1);
        }

        private void sort(int start, int end) {
            if (start >= end) {
                return;
            }

            int mid = (start + end) / 2;
            sort(start, mid);
            sort(mid+1, end);
            merge(start, end);
        }

        private void merge(int start, int end) {
            int mid = (start + end) / 2;
            int left = start;
            int right = mid+1;
            int cur = 0;

            for (; left <= mid && right <= end; cur++) {
                if (originalArray[left] < originalArray[right]) {
                    buffer[cur] = originalArray[left];
                    left++;
                } else {
                    buffer[cur] = originalArray[right];
                    right++;
                }
            }

            for (; left <= mid; cur++, left++) {
                buffer[cur] = originalArray[left];
            }

            for (; right <= end; cur++, right++) {
                buffer[cur] = originalArray[right];
            }

            System.arraycopy(buffer, 0, originalArray, start, cur);
        }
    }
}

Merge sort is easily parallelizable algorithm. It is more efficient than quicksort on linked lists where it can be implemented using only constant space.

Quicksort

Idea: split array in two parts by comparing each element to the pivot, then recursively sort these parts. Because quicksort depends on the contents of array, it is possible to construct such array that will force this algorithm to work quadratic time. Though this problem is easily solved by choosing random element, to be precise it is necessary to say that this algorithm has O(nlog(n)) time complexity in the average case and O(n^2) time complexity in the worst case. Space complexity is O(log(n)) in the average case and O(n) in the worst case since this algorithm is recursive.

Another delicate part of quicksort is how to partition array in constant space. In order to do that create hiStart pointer which will store index of the beginning of the second part of the array. Then iterate over the array comparing items to pivot: if current item is less than pivot, swap it with the item at hiStart and increment hiStart.

To speed up quicksort in the situation of repeated items one could implement splitting into three parts: less than, equal to and greater than pivot. It requires one more pointer, loEnd which will store index of the end of the first part.

The implementation below chooses random pivot and uses two-way partition. It is not stable, however, it is possible to make quicksort stable, but it requires additional O(n) space. This implementation use O(1) space.

package com.dancingrobot84.algorithms.sorting;

import com.dancingrobot84.algorithms.util.ArraysExt;
import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void sort(int[] array) {
        sort(array, 0, array.length-1);
    }

    private static Random generator = new Random();

    private static void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivotIndex = partition(array, start, end);
        sort(array, start, pivotIndex);
        sort(array, pivotIndex+1, end);
    }

    private static int partition(int[] array, int start, int end) {
        int pivotIndex = start + generator.nextInt(end - start);
        int pivot = array[pivotIndex];
        ArraysExt.swap(array, pivotIndex, end);

        int hiStart = start;
        for (int i = start; i < end; i++) {
            if (array[i] < pivot) {
                ArraysExt.swap(array, hiStart, i);
                hiStart += 1;
            }
        }

        ArraysExt.swap(array, hiStart, end);
        return hiStart;
    }
}

Quicksort has better constant than merge sort and heap sort. When implemented well it could outperform its competitors drastically. It is possible to parallelize quicksort, but it is a bit harder to do than in case of merge sort.

Heap sort

Idea: build a heap on input array, then iteratively take minimal element out of it until there is no items left. Since building a heap has O(n) time complexity and retrieving minimal element from it requires O(log(n)) time overall time complexity for this sorting algorithm is O(nlog(n)). This algorithm is not stable.

This idea could be used on any data structure which supports building in O(nlog(n)) or faster and retrieving minimum/maximum in O(log(n)). Heap is preferred because it is possible to build heap on the same input array, thus spending only O(1) space.

package com.dancingrobot84.algorithms.sorting;

import com.dancingrobot84.algorithms.datastructures.Heap;
import com.dancingrobot84.algorithms.datastructures.impl.BinaryHeap;
import com.dancingrobot84.algorithms.util.ArraysExt;
import java.util.Arrays;

public class HeapSort {
    public static void sort(Integer[] array) {
        Heap<Integer> heap = BinaryHeap.fromArray(array);
        int i = array.length - 1;
        while (heap.size() > 0) {
            array[i] = heap.pop();
            i--;
        }
        ArraysExt.reverse(array);
    }
}

Linear time algorithms

Linear time sorting algorithms do not compare elements or they would work in O(nlog(n)). Instead, they either require some constraints on input or use some knowledge about items of an array. They usually used in complex algorithms to cut some time here and there, e.g. building suffix arrays or for sorting data on parallel clusters.

Counting sort

Assumption: all items of input array belong to some finite set of items or could be uniquely associated with a key from this finite set. Denote the size of such set as k.

Idea: iterate over input array counting how many times each distinct item occurs here, then using this information put items in their places. To store occurences we need array of integers of length k and output array of length n, thus we need O(n+k) space. Both of these array are traversed during the execution of algorithm, so its time complexity is O(n+k) too.

package com.dancingrobot84.algorithms.sorting;

import java.util.Arrays;

public class CountingSort {
    public static final int K = 100;

    public static void sort(int[] array) {
        int[] counter = new int[K];
        for (int item: array) {
            counter[item]++;
        }

        int totalCount = 0;
        for (int i = 0; i < K; i++) {
            int oldCount = counter[i];
            counter[i] = totalCount;
            totalCount += oldCount;
        }

        int[] arrayCopy = Arrays.copyOf(array, array.length);
        for (int item: arrayCopy) {
            array[counter[item]] = item;
            counter[item]++;
        }
    }
}

Radix sort

Assumption: each item from input array should be represented in positional notation, i.e. as a collection of characters from finite alphabet of size k where the power of each character depends on where it is placed within a collection. Examples of positional notation are binary and decimal numbers and strings.

Idea: sort input items by a single character in fixed position for all possible positions, e.g. sort by 1st character, then by 2nd, continue until all m positions were used to sort items. Sorting at specified position could be performed using counting sort since alphabet is finite, therefore it takes O(m(n+k)) time and O(mn) space to sort the whole array.

Depending on the starting position radix sort could be LSD (least significant digits first) or MSD (most significant digits first). The first one is used to sort in representation order (correct for decimals), the second one is for sorting in lexicographic order. The implementation below is LSD radix sort.

package com.dancingrobot84.algorithms.sorting;

import java.util.Arrays;

public class RadixSort {
    public static final int K = 2;
    public static final int M = 32;

    public static void sort(int[] array) {
        int[] temp = array;
        for (int i = 0; i < M; i++) {
            temp = sort(temp, i);
        }
        System.arraycopy(temp, 0, array, 0, array.length);
    }

    private static int[] sort(int[] array, int bit) {
        int[] counter = new int[K];
        for (int i = 0; i < array.length; i++) {
            counter[getBit(array[i], bit)]++;
        }

        int totalCount = 0;
        for (int i = 0; i < K; i++) {
            int oldCount = counter[i];
            counter[i] = totalCount;
            totalCount += oldCount;
        }

        int[] result = new int[array.length];
        for (int item: array) {
            result[counter[getBit(item, bit)]] = item;
            counter[getBit(item, bit)]++;
        }
        return result;
    }

    private static int getBit(int n, int k) {
        return (n >> k) & 1;
    }
}

Algorithms comparison chart

1. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms

2. Sorting - topcoder