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:

- Sort the input to pre-process data and make the solution simpler and more efficient
- 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:

- Be familiar with the main sorting algorithms
- 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).

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;
}
```

**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.**

Have you ever wondered why the meaning of sorting in computing (ordering or ranking) is different from its everyday meaning (dividing into piles or categories)? The answer has to do with the history of sorting going back 130 years and turns out to be really interesting.

— Arvind Narayanan (@random_walker) September 3, 2018

Liked this article? Share it with others: