A stable and adaptive quadratic sorting algorithm. [Best: O(n), Average: O(n²), Worst: O(n²), Space: O(1)]

Idea

The idea of insertion sort is to start with a sorted array of the first item on the left, and move one unsorted item to correct position by comparing with the sorted items, and repeat until all items are sorted.

There are two noteworthy advantages of insertion sort. First, insertion sort is stable in nature. The relative order of items with equal key remains unchanged before and after sorting. Second, insertion sort is very efficient on almost already sorted arrays.

First Implementation in Go

Below is my first implementation. It’s concise since I can perform the swaps without temporary variable, thanks to golang’s parallel assignment.

insertion_sort.gosource

package sorting

func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
			arr[j], arr[j-1] = arr[j-1], arr[j]
		}
	}
}

Optimization

The above implementation leaves rooms for performance tuning. In the outer loop, to move an item with k swaps takes 2k operations. It can be cut down to half by shifting each item to its neighbor with only k operations.

insertion_sort_optimized.gosource

package sorting

func OptimizedInsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		unsorted := arr[i]
		j := i - 1
		for ; j >= 0 && unsorted < arr[j]; j-- {
			arr[j+1] = arr[j]
		}
		arr[j+1] = unsorted
	}
}

With the help of go benchmark tool, we see a constant performance growth of around 2x after optimization.

► go test -bench=.
BenchmarkOptimizedInsertionSort100-8            10000000               120 ns/op
BenchmarkOptimizedInsertionSort1000-8            1000000              1075 ns/op
BenchmarkOptimizedInsertionSort10000-8            100000             10584 ns/op
BenchmarkInsertionSort100-8                     10000000               204 ns/op
BenchmarkInsertionSort1000-8                     1000000              1916 ns/op
BenchmarkInsertionSort10000-8                     100000             19044 ns/op
PASS
ok      github.com/billjh/algo/sorting  10.389s

References:

1. https://en.wikipedia.org/wiki/Insertion_sort
2. https://github.com/billjh/algo/tree/master/sorting
3. https://betterexplained.com/articles/sorting-algorithms/#Insertion_Sort_Best_ON_WorstON2
4. https://golang.org/pkg/testing/#hdr-Benchmarks

---

#algorithms #sorting #golang

Thursday, Feb 16 2017