<blockquote>
<p>It seems to run about twice as fast as the native sort function in golang</p>
</blockquote>
<p>Note that the native sort for slice will evolve with Go 1.19 (Q4 2022).<br />
See:</p>
<ul>
<li><a href="https://github.com/golang/go/issues/50154" rel="nofollow noreferrer">issue 50154</a>,</li>
<li><a href="https://go-review.googlesource.com/c/exp/+/399315/" rel="nofollow noreferrer">CL 399315</a>,</li>
<li><a href="https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257" rel="nofollow noreferrer">commit 72e77a7</a> by <a href="https://github.com/zhangyunhao116" rel="nofollow noreferrer">ZhangYunHao</a>.</li>
</ul>
<blockquote>
<h2>sort: use pdqsort</h2>
<ul>
<li>Across all benchmarks, pdqsort is never significantly slower than the previous algorithm.</li>
<li>In common patterns, pdqsort is often faster (i.e. 10x faster in sorted slices).</li>
</ul>
<p>The <code>pdqsort</code> is described at <a href="https://arxiv.org/pdf/2106.05123.pdf" rel="nofollow noreferrer">Pattern-defeating Quicksort (pdf)</a> by <strong><a href="https://github.com/orlp" rel="nofollow noreferrer">Orson R. L. Peters</a></strong>.</p>
<p>(extract)<br />
Pattern-defeating
quicksort is often the best choice of algorithm overall for small to medium input sizes or data type sizes.<br />
It and other quicksort variants suffer from datasets that
are too large to fit in cache, where is4o shines.<br />
The latter algorithm however suffers from bad performance on smaller sizes, future research could perhaps combine the best of these two algorithms</p>
<p>This CL is inspired by both C++ implementation and Rust implementation.</p>
<ul>
<li><a href="https://github.com/orlp/pdqsort" rel="nofollow noreferrer">C++ implementation</a></li>
<li><a href="https://docs.rs/pdqsort/latest/pdqsort/" rel="nofollow noreferrer">Rust implementation</a></li>
</ul>
</blockquote>
Golang custom sort is faster than native sort
<p>I was just playing around with sorting in golang and I found a qsort function on stackoverflow. It seems to run about twice as fast as the native sort function in golang. I've tried it with different input sizes and tested that it works.</p>

<p>Could anyone explain why this happens?</p>

<p>Here is the code you can test it on your pc:</p>

<pre><code>package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

func qsort(a []int) []int {
    if len(a) &lt; 2 {
        return a
    }

    left, right := 0, len(a)-1

    // Pick a pivot
    pivotIndex := rand.Int() % len(a)

    // Move the pivot to the right
    a[pivotIndex], a[right] = a[right], a[pivotIndex]

    // Pile elements smaller than the pivot on the left
    for i := range a {
        if a[i] &lt; a[right] {
            a[i], a[left] = a[left], a[i]
            left++
        }
    }

    // Place the pivot after the last smaller element
    a[left], a[right] = a[right], a[left]

    // Go down the rabbit hole
    qsort(a[:left])
    qsort(a[left+1:])

    return a
}

func main() {
    // Create an array with random integers
    rand.Seed(30)
    size := 1000000
    array1 := make([]int, size)
    start := time.Now()

    for i, _ := range array1 {
        array1[i] = rand.Int()
    }

    fmt.Println("Creating array with ", size, " elements...")
    fmt.Println("--- ", time.Since(start), " ---")
    // Create a copy of the unsorted array
    array2 := make([]int, size)
    copy(array2, array1)

    // Short using native function
    start = time.Now()
    sort.Ints(array1)

    fmt.Println("Sorting with the native sort...")
    fmt.Println("--- ", time.Since(start), " ---")

    // Sort using custom qsort
    start = time.Now()
    qsort(array2)

    fmt.Println("Sorting with custom qsort...")
    fmt.Println("--- ", time.Since(start), " ---")

}
</code></pre>