Sorting Boot Camp

Bootcamp Sorting

Sorting algorithms are some of the most common and important algorithms in computer science. They appear in a variety of algorithmic problems and understanding time and space complexity of the most common algorithms will help you find the optimal solution to many interview questions.

Arranging items in ascending or descending order is commonly used to speed up search (ie. binary search) and identify similar items.

Typically there are two types of sorting problems:

  1. Sort the input to pre-process data and make the solution simpler and more efficient
  2. Implement a custom ordering of the input elements (usually using a heap, BST or array indexed by value)

To be well prepared to tackle sorting problems you have to:

  1. Be familiar with the main sorting algorithms
  2. Be familiar with your language of choice sorting libraries

In Java you can sort arrays with Arrays.sort(A) and lists with Collections.sort(L). The time complexity of Arrays.sort(A) is O(nlogn) (where n is the length of the array) and the space complexity is O(n).

Collections.sort(L) uses Arrays.sort(A) internally after converting the list to an array, and then copy the array A back to the list L. For this reason the time complexity is O(nlogn) and the space complexity is O(n).

Sorting algorithms

Here is a list of the classic algorithms you need to know. You probably won’t be asked to code any of them during an interview (even though I was asked to code MergeSort in the first part of a Google interview) but the practice and confidence in coding these algorithms will help you while working on your solution.

Quick Sort

Pick a pivot element and reorder array putting elements less than the pivot to the left of the pivot (partitioning). Apply recursively to the left and right sub-arrays.

Time: O(n^2) worst case - O(nlogn) average case
Space: O(logn)
In place?: yes
Stable?: no

Merge Sort

Divide input array in 2 equal parts, until the length of each sub-array is 1 and then merge the left and right sub-arrays (Divide and Conquer approach).

Time: O(nlogn)
Space: O(n)
In place?: no
Stable?: yes

Heap Sort

Build a Heap from input array. Repeatedly remove the top of the heap and insert element in a separate array.

Time: O(nlogn)
Space: O(n)
In place?: yes
Stable?: no

Selection Sort

Divide input array in two parts. Keep the left sub-array sorted and repeatedly pick the smallest element from the unsorted sub-array and insert in the sorted sub-array at the right place.

Time: O(n^2)
Space: O(1)
In place?: yes
Stable?: no

Bubble Sort

Repeatedly step through the input array and compare pair of elements, swapping them if needed to keep the lowest element to the left. Repeat until the list is sorted.

Time: O(n^2)
Space: O(1)
In place?: yes
Stable?: yes

Counting Sort

Loop through the array once and keep count of the occurrence of each unique key. Use arithmetic to calculate the correct position of each key. Very efficient if the number of distinct keys is small.

Time: O(n+k) - k = range of input
Space: O(n+k)
In place?: yes
Stable?: yes

Insertion Sort

Iterate the array inserting one item at a time in the correct position in the array. Efficient in practice for arrays of 10 elements or less.

Time: O(n^2)
Space: O(1)
In place?: yes
Stable?: yes

Radix Sort

Take the most significant digit of each element. Group elements based on that digit and sort each bucket recursively starting with the next digit to the right. Concatenate the buckets in order.

Time: O(kn) k = number of bits required to store each element
Space: O(n+k)
In place?: no
Stable?: yes

Bucket Sort

Distribute elements into a bucket (Scatter) and sort each bucket individually. Visit the buckets in order and put all elements back in the original array (Gather).

Time: O(n^2)
Space: O(n)
In place?: yes
Stable?: yes

An important property of sorted arrays is that it’s possible to search for a specific element in O(logn) by performing binary search. Binary search can be implemented iteratively by splitting the array in 2 until the mid element is equal to the element we are searching for. You should practice writing BinarySearch as many times needed until you are very comfortable with its implementation and edge cases.

int binarySearch(int[] A, int k) {

    int start = 0;
    int end = A.length-1;

    while (start <= end) {
        int mid = Math.floor(start+end)/2);

        if (A[mid].equals(k) {
            return mid;
        } else {
            if (A[mid] < k) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
    }

    return -1;
}

Glossary

in place algorithm: one which uses O(1) space.

stable algorithm: a stable algorithms preserves the relative order of the original input, so that items that are equal appear in the output in the same order they appeared in the input.

online algorithm: is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start (Insertion Sort is an example of online algorithm).

Fun fact Why does sorting in computer science mean ordering rather than categorizing? Click on the tweet below to read the full story on Twitter.

Back to homepage