In this article, I’ll review the following 8 classical sorting algorithms, and implement them in Go:

• bubble sort
• selection sort
• insertion sort
• shell sort
• merge sort
• quick sort
• heap sort

These basic sorting algorithms are sometimes favored by interviewers, and the ideas of these classical sorting algorithms(like merge sort, quick sort, heap sort, etc.) are sometimes the key points of algorithm problems, so it’s worth taking time on it.

## Highly inefficient sorts

### Bubble sort

Bubble sort is simple but highly inefficient, so it’s rarely used in practice, unless in situation where inputs data is very small or nearly sorted.

The algorithms is to compare adjsent two numbers, swap them if first is larger than second, from beginning to end. Every time the biggest so far will pop to the right, and every time it takes O(n) time complexity and it needs n times, so the time complexity is O(n2). ``````1 2 3 4 5 6 7 8 9 `````` ``````func bubbleSort(nums []int) { for i, size := 0, len(nums); i < size; i++ { for j := 0; j < size-i-1; j++ { if nums[j] > nums[j+1] { nums[j], nums[j+1] = nums[j+1], nums[j] } } } } ``````

## Simple sorts

Two of the simplest sorts are insertion sort and selection sort, both of which are efficient on small data.

### Selection sort

Selection sort is very simple:

1. find the minimum in the list
2. swap with the i index

Its time complexity is O(n2). `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````func selectionSort(nums []int) { for i := 0; i < len(nums)-1; i++ { minIndex := i for j := i + 1; j < len(nums); j++ { if nums[j] < nums[minIndex] { minIndex = j } } nums[i], nums[minIndex] = nums[minIndex], nums[i] } } ``````

### Insertion sort

Insertion sort is used in cases where the input data is small or partly sorted. The idea is to pick one from unsorted list and insert into sorted part.

Its time complexity is O(n2). ``````1 2 3 4 5 6 7 `````` ``````func insertSort(nums []int) { for i := 1; i < len(nums); i++ { for j := i; j > 0 && nums[j] < nums[j-1]; j-- { nums[j], nums[j-1] = nums[j-1], nums[j] } } } ``````

### Shell sort

Shell sort improves upon insertion sort by moving out of order elements more than one position at a time. It will separate data by gap and sort each group by insertion sort, and continously decrease gap until it reaches 1, in that case it becomes insertion sort completely. ``````1 2 3 4 5 6 7 8 9 `````` ``````func insertShellSort(nums []int) { for gap := len(nums) / 2; gap > 0; gap /= 2 { for i := gap; i < len(nums); i++ { for j := i; j >= gap && nums[j] < nums[j-gap]; j -= gap { nums[j], nums[j-gap] = nums[j-gap], nums[j] } } } } ``````

## Efficient sorts

### Heap sort

Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree.

Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity. `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````func heapSort(nums []int) { heapify(nums) for i := len(nums) - 1; i > 0; i-- { nums[i], nums = nums, nums[i] siftDown(nums, 0, i) } } // modify nums to max heap func heapify(nums []int) { for i := len(nums) / 2; i >= 0; i-- { siftDown(nums, i, len(nums)) } } func siftDown(heap []int, lo, hi int) { root := lo for { child := 2*root + 1 if child >= hi { return } if child+1 < hi && heap[child+1] > heap[child] { child++ } if heap[child] > heap[root] { heap[child], heap[root] = heap[root], heap[child] root = child } else { return } } } ``````

### Merge sort

The concept of merge sort: Divide and Conquer is widely used for solving other questions. Basically it works as follows:

1. If the length of list is smaller or equal than 1, it’s sorted
2. Divide the list to two sublist and sort them recursively
3. Merge two sorted list into one

Its time complexity is O(n2), and it needs O(n) space. `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 `````` ``````func mergeSort(nums []int) { if len(nums) <= 1 { return } middle := len(nums) / 2 mergeSort(nums[:middle]) mergeSort(nums[middle:]) merge(nums, middle) } func merge(nums []int, middle int) { tmp := make([]int, len(nums)) i, j, k := 0, middle, 0 for i < middle && j < len(nums) { if nums[i] < nums[j] { tmp[k] = nums[i] i++ } else { tmp[k] = nums[j] j++ } k++ } for i < middle { tmp[k] = nums[i] k, i = k+1, i+1 } for j < len(nums) { tmp[k] = nums[j] k, j = k+1, j+1 } for i, v := range tmp { nums[i] = v } } ``````

### Quick sort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array, an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in-place. The lesser and greater sublists are then recursively sorted. This yields average time complexity of O(n log n), with low overhead, and thus this is a popular algorithm. `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````func quickSort(nums []int) { if len(nums) == 0 { return } i, j, pivot := 0, len(nums)-1, nums for i < j { for i < j && nums[j] >= pivot { j-- } if i < j { nums[i], i = nums[j], i+1 } for i < j && nums[i] < pivot { i++ } if i < j { nums[j], j = nums[i], j-1 } } nums[i] = pivot quickSort(nums[:i]) quickSort(nums[i+1:]) } ``````

## Non-comparison sorts `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 `````` ``````func radixSort(nums []int) { // bucket stores nums in new place, count stores count number of every digit bucket, count := make([]int, len(nums)), make([]int, 10) // start from the least significant digit(lsd) for d := 1; d <= maxBitLen(nums); d++ { // zeros the count for i := range count { count[i] = 0 } // count numbers of every digit for _, n := range nums { count[digit(n, d)]++ } for i := 1; i < 10; i++ { count[i] += count[i-1] } for i := len(nums) - 1; i >= 0; i-- { k := digit(nums[i], d) count[k]-- bucket[count[k]] = nums[i] } for i, v := range bucket { nums[i] = v } } } // Find the max digit length among all numbers in nums func maxBitLen(nums []int) int { var max int for _, v := range nums { if v > max { max = v } } var ret int for max > 0 { ret, max = ret+1, max/10 } return ret } // Find digit of number n at index d func digit(n, d int) int { pow := 1 for d > 1 { pow, d = pow*10, d-1 } return n / pow % 10 } ``````