Introducing sorting algorithms in Go
Insertion Sort
When players of card games like Rummy or bridge pick up a new hand, they often insert new cards into their hand one by one by making room at the position where the new card fits to create a sorted hand. To do this, they move the lower value cards to the left and higher value cards to the right and insert the new card into the space created (Figure 3). This is also how the insertion sort algorithm [1] works, a procedure that sorts inplace with only a few lines of code, but requires some mental dexterity.
The algorithm divides the array to be sorted into two sections: on the left, the elements already sorted so far; on the right, the unsorted elements. To do this, it determines the element to be examined, starting with the second element of the array. In Figure 4 (top), this is initially the number 4. To the left of it, the previously sorted list contains only the 3; to the right of it, what is – thus far – the unsorted part then follows, starting with a 1. Now a loop starts going left to check where to insert the current element into the sorted section. Since the current element (the 4) is larger than the only sorted element to its left, there is nothing else to do – the algorithm proceeds to the next element.
In the next step in Figure 4 (bottom), the number 1 is the current element, and the loop hops over to the left to check where to insert it in the sorted part. It first sees the 4, determines that the current element (1) must be to the left of it, and moves the 4 one place to the right as shown in step (a), in place of the current element that was previously saved in a variable. Further to the left, it then sees the 3, which also needs to be on the right of the current element, and then moves the 3 to the position previously occupied by the 4 as shown in step (b). Now there is nothing standing in the way of the 1 previously stashed away in a variable; it can move to the first position in the array as shown in step (c). The sequence is now 134…, and the algorithm proceeds by inspecting the 2 as the current element. Lather, rinse, repeat.
Listing 4 implements the whole thing in a relatively compact way. The for
loop in line 11 determines the current element, starting at j=1
(i.e., the second element of the array starting at index position 0). Listing 4's output with the various sorting steps and their current key
elements in each case is shown in Figure 5.
Listing 4
insert.go
01 package main 02 03 import ( 04 "fmt" 05 ) 06 07 func main() { 08 things := []int{3, 4, 1, 2, 6, 5, 8, 7} 09 fmt.Printf("%+v\n", things) 10 11 for j := 1; j < len(things); j++ { 12 key := things[j] 13 fmt.Printf("key=%d\n", key) 14 i := j  1 15 for i >= 0 && things[i] > key { 16 things[i+1] = things[i] 17 i 18 } 19 things[i+1] = key 20 fmt.Printf("%+v\n", things) 21 } 22 }
The test loop, which jumps to the left to make room in the sorted part, starts at i=j1
in line 14. It continues until it encounters a sorted element that is less than or equal to the current element, or until it risks dropping off on the left end of the array at i<0
. In each round of the loop, line 16 copies an element in the sorted section one place to the right, and i
is decremented by one. At the end of the loop, line 19 copies the current element cached in key
to the vacant position, and the outer for
loop moves on to the next round.
However, the number of steps required by insertion sort increases proportionally to the square of the number of elements. The algorithm therefore does not work faster than a bubble sort. For randomly structured input data, there are definitely smarter methods that reduce the number of steps from O(n2) to O(n*lg(n)).
Merge Sort
Better methods often rely on the "divide and conquer" principle. This means that they do not solve the whole problem in one go, but divide it into two more easily solvable partial problems, which they then tackle recursively.
What I like about merge sort is its almost trivial implementation based on plain vanilla recursion. The trick is to cut the array in half, sort the two halves individually, and then merge the two sorted stacks into a new one resulting in a larger sorted stack. The individual "sorting" procedure is not really sorting at all: The sorting function again chops the array in half and calls itself against the two halves until it deals with an array with only one element. The function declares this as sorted and returns it without change.
The real grit of the procedure is in the merge()
function, which merges two sorted arrays. To do this, it walks through the elements of the two sorted stacks, compares their two top elements, removes the smaller one, and puts it on the result stack. Figure 6 illustrates the procedure with a card game that combines the two upper sorted stacks to create the stack at the bottom, which ends up to be sorted as well.
In Listing 5, the merge()
function starting in line 24 expects an integer array a
, as well as three index positions: p
, q
, and r
. The two partial arrays that merge()
has to join are available at the positions p
through q
and q+1
through r
. The function then goes ahead and stores the results in place in the original array a
.
Listing 5
merge.go
01 package main 02 03 import ( 04 "fmt" 05 ) 06 07 func main() { 08 things := []int{17, 34, 42, 1, 7, 9, 8} 09 10 fmt.Printf("%+v\n", things) 11 mergesort(things, 0, len(things)1) 12 fmt.Printf("%+v\n", things) 13 } 14 15 func mergesort(a []int, p, r int) { 16 if p < r { 17 q := (p + r) / 2 18 mergesort(a, p, q) 19 mergesort(a, q+1, r) 20 merge(a, p, q, r) 21 } 22 } 23 24 func merge(a []int, p, q, r int) { 25 left := make([]int, qp+1) 26 right := make([]int, rq) 27 28 copy(left, a[p:]) 29 copy(right, a[q+1:]) 30 31 fmt.Printf("left=%d\n", left) 32 fmt.Printf("right=%d\n", right) 33 34 lidx := 0 35 ridx := 0 36 oidx := p 37 38 for lidx < len(left) && 39 ridx < len(right) { 40 if left[lidx] < right[ridx] { 41 a[oidx] = left[lidx] 42 lidx++ 43 } else { 44 a[oidx] = right[ridx] 45 ridx++ 46 } 47 oidx++ 48 } 49 for lidx < len(left) { 50 a[oidx] = left[lidx] 51 lidx++ 52 oidx++ 53 } 54 for ridx < len(right) { 55 a[oidx] = right[ridx] 56 ridx++ 57 oidx++ 58 } 59 }
This presupposes that merge()
first creates a copy of the left and right array in the variables left
and right
. The function uses make()
to allocate memory for arrays of the desired length. Then, starting in line 28, it calls the builtin copy()
function and passes it the arrays to be copied as a[p:]
("Element at index p
and following") and a[q+1:]
("Element at index q+1
and following"). Note that we don't want copy()
to actually copy all following elements, but make use of the fact that copy()
only copies as many characters as will fit into the target array, specified as the first parameter. But since we've allocated left
and right
correctly with their required lengths previously, the number of characters actually copied is also correct.
Then the for
loop runs through the two arrays starting in line 38, removes the smaller current element from the corresponding stack, and terminates if either one is depleted. The remaining elements of the other array are then copied into the resulting array one by one by the two for
loops starting in line 49 or 54.
The main mergesort()
function in line 15, which expects the unsorted array, as well as the index positions of start and end, only needs to chop the array passed to it into two parts, call itself recursively against the two subfields, and call merge()
to merge the two results. The recursion is repeated until mergesort()
receives an array with only one element (then p == r
and the if
condition is false) whereupon mergesort()
simply returns, because this oneelement array is sorted by definition. Figure 7 shows how the algorithm gradually sorts an array of seven integers and prints out the result.
BuiltIn
Normally, however, aside from coding interviews, software engineers never really code up their own sorting algorithms in Go. The language offers builtin sorting functions for slices of strings, integers, or floats. After importing the sort
package (Listing 6), sort.Ints()
, sort.Float64s
, and sort.Strings()
are available, each of which arranges a slice of integers or floatingpoint numbers or strings in ascending order by sorting the array passed to it in place.
Listing 6
stringsort.go
01 package main 02 03 import ( 04 "fmt" 05 "sort" 06 ) 07 08 func main() { 09 things := []string{"green", "red", "blue", "black", "white"} 10 11 sort.Strings(things) 12 13 fmt.Printf("%+v\n", things) 14 }
As you can see from the source code [5] on the Go website, the language uses the quicksort algorithm internally. This is a divideandconquer mechanism that runs at breakneck speed virtually everywhere. Usually it only takes O(n*log(n)) steps to reach its goal. On rare occasions, however, it freaks out completely to the tune of O(n2) complexity – with a million entries; this could mean the difference between seconds and years.
If the algorithm has to terminate with 100 percent assurance, other methods sometimes turn out to be more advantageous. However, in order to fend off such outliers, standard libraries of programming languages often include procedures that slightly modify the algorithm and avert worst case scenarios.
« Previous 1 2 3 Next »
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Direct Download
Read full article as PDF:
Price $2.95
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Find SysAdmin Jobs
News

KDE Plasma 5.27 Beta is Ready for Testing
The latest beta iteration of the KDE Plasma desktop is now available and includes some important additions and fixes.

Netrunner OS 23 Is Now Available
The latest version of this Linux distribution is now based on Debian Bullseye and is ready for installation and finally hits the KDE 5.20 branch of the desktop.

New Linux Distribution Built for Gamers
With a Gnome desktop that offers different layouts and a custom kernel, PikaOS is a great option for gamers of all types.

System76 Beefs Up Popular Pangolin Laptop
The darling of opensourcepowered laptops and desktops will soon drop a new AMD Ryzen 7powered version of their popular Pangolin laptop.

Nobara Project Is a Modified Version of Fedora with UserFriendly Fixes
If you're looking for a version of Fedora that includes thirdparty and proprietary packages, look no further than the Nobara Project.

Gnome 44 Now Has a Release Date
Gnome 44 will be officially released on March 22, 2023.

Nitrux 2.6 Available with Kernel 6.1 and a Major Change
The developers of Nitrux have officially released version 2.6 of their Linux distribution with plenty of new features to excite users.

Vanilla OS Initial Release Is Now Available
A stock GNOME experience with ondemand immutability finally sees its first production release.

Critical Linux Vulnerability Found to Impact SMB Servers
A Linux vulnerability with a CVSS score of 10 has been found to affect SMB servers and can lead to remote code execution.

Linux Mint 21.1 Now Available with Plenty of Look and Feel Changes
Vera has arrived and although it is still using kernel 5.15, there are plenty of improvements sure to please everyone.