Hands-On High Performance with Go

O(n log n) – quasilinear time

Algorithms written in quasilinear (or log-linear) time are often used to order values within an array in Go.

Some examples of quasilinear time are as follows:

• The average case time complexity for Quicksort
• The average case time complexity for Mergesort
• The average case time complexity for Heapsort
• The average case time complexity for Timsort

The normalized timings for quasilinear time can be found in the following table:

Number of items in the dataset	Resulting computation time
10	10 seconds
100	200 seconds
1,000	3,000 seconds

You'll see a familiar pattern here. This algorithm follows a pattern that's similar to the O(log n) algorithm. The only thing that changes here is the ...