Hands-On High Performance with Go

Quick sort

The Go standard library has a quick sort algorithm, as we saw in the O( n log n) – quasilinear time section. QuickSort was initially implemented in Unix as the default sort routine in the standard library. From there, it was built upon and used as qsort in the C programming language. Because of its familiarity and vast history, it is commonly used as a sorting algorithm in many computer science problems today. Using our algorithms table, we can deduce that a standard implementation of the quickSort algorithm has an average time complexity of O(n log n). It also has the added benefit of using, at worst, an O(log n) space complexity, making it ideal for in-place moves.

Now that we are done with sort algorithms, we will move on to ...