POSTS
Insertion Sort in Go (Golang) with test
What is Insertion Sort?
Insertion sort is one of the simplest sorting algorithm. It breaks the input into sorted and unsorted list, picks next element from unsorted list and puts it into right place in sorted list.
Let’s break this down into concrete steps 
 iterate over the array n  1 times that is from index 1 to n1
 in each iteration let’s say i, pick i+1^{th} element and put it into existing sorted list [0, i] such that the resultant list [0, i+1] is also sorted
Implementation
Let’s create a new directory inside $GOPATH/src
. I’ve called it gochronicles.devcode
.
Now let’s create new file insertion_sort.go
. You can organise it whichever way you feel comfortable.
I’ve put it up in algorithms/sorting


Let’s Test
If this is first time you are setting up test in Go then please refer this section of my earlier post.
Let’s create a new file insertion_sort_test.go
in the same directory as insertion_sort.go
There’s convention in Go to define got
and want
variables in each test.
got
defines the result we get after execution of function under test.
want
defines the expected output.
We then compare got
and want
.
If they are equal, our test has passed else we raise an error using t.Errorf
thereby failing our test.
Since we are comparing slices we’ll use reflect.DeepEqual
which in case of slices verifies equality of each item in the list.
We can run our tests using go test
if we are running it from directory which contains the test files.


If you use go test v count=1 ./...
then it’ll run all the tests under current and subdirectories recursively.
So if you followed my earlier post as well, running this command
will now run test for both bubble and insertion sort.
To run specific set of tests, go test
provides run
flag whose value can be a regex.
So let’s use go test v count=1 run="Insertion*" ./...
to run tests which has Insertion
in their names.


You can find the full source code for this on Github.
Complexity
Worst Case Time Complexity : O(n^{2})
Best Case Time Complexity : O(n)
Space Complexity : O(1) and hence its an inplace sorting algorithm.
Stable : yes as it does not change the relative order of elements with equal keys