Multithreaded Quicksort in Go and in C

Multithreading is an important issue with stagnating single-thread performance and multicore CPUs. This tutorial tries to show how to distribute a calculation task among threads and thus speed up the calculation.

This is not possible for every algorithm. But Quicksort for example is a Divide and Conquer algorithm. This type of algorithm is usually well suited for parallelization.

Singlethreaded Quicksort in Go

This Quicksort is implemented recursively with tail call elimination. This means that after partitioning, one subarray is sorted recursively and the other in the current context in the program loop. The smaller subarray is sorted first so that this recursive implementation is stack-safe (avoids a possible stack overflow).

If the subarray becomes smaller than 30, it switches to insert sorting, as this is faster for small arrays.

package main

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

func InsertSort(data[] int) {

    i := 1
    for i < len(data) {
        h := data[i]
        j := i - 1
        for j >= 0 && h < data[j] {
            data[j + 1] = data[j]
            j -= 1
        }
        data[j + 1] = h
        i += 1
    }
}

func median3(d []int) {
    lo := 0
    hi := len(d) - 1
    mid := hi / 2

    if d[mid] < d[lo] {
        d[mid], d[lo] = d[lo], d[mid]
    }
    if d[hi] < d[lo] {
        d[hi], d[lo] = d[lo], d[hi]
    }
    if d[hi] < d[mid] {
        d[hi], d[mid] = d[mid], d[hi]
    }
    d[0], d[mid] = d[mid], d[0]
}

func Partition(data[] int) ([] int, [] int) {
    median3(data)
    piv := data[0]
    mid := 0
    i := 1
    for i < len(data) {
        if data[i] < piv {
            mid += 1
            data[i], data[mid] = data[mid], data[i]
        }
        i += 1
    }
    data[0], data[mid] = data[mid], data[0]

    if mid < len(data) / 2 {
        return data[:mid], data[mid + 1:]
    } else {
        return data[mid + 1:], data[:mid]
    }
}

func QSort(data[] int) {

    var data2[] int
    for len(data) >= 30 {
        data2, data = Partition(data)
        QSort(data2)
    }
    InsertSort(data)
}

func RandomInit(data[] int) {

    for i := 0; i < len(data); i++ {
        data[i] = rand.Intn(1000000000)
    }
}

func main() {

    const LEN = 50000000
    var data[LEN] int
    RandomInit(data[:])
    fmt.Printf("Sorting %d million numbers with Quicksort in Go ...\n",
        LEN / 1000000)
    start := time.Now()
    QSort(data[:])
    fmt.Printf("Time: %.2fs\n", time.Since(start).Seconds())
}

Sorting 50 million numbers with Quicksort in Go ...
Time: 3.75s

import (
    .
    .
    "sort"
)

    .
    sort.Ints(data0[:])
    .

Sorting 50 million numbers with sort.Ints ...
Time: 4.20s

Multithreaded Quicksort in Go

After the partition function, we have two independent arrays that can be sorted in parallel.

Starting a Goroutine, the light Go version of a thread, takes time and space. Therefore we start Goroutines only for larger arrays and if not too many goroutines are active.

With go the Goroutine is started. A sync.WaitGroup variable, which is shared between all running Goroutines, is used to count the active Goroutines. When the last Goroutine has finished its work, all the work is done.

package main
import (
    "fmt"
    "time"
    "math/rand"
    "sync"
    "runtime"
)
.
.
.
func QuSort(data[] int, wg *sync.WaitGroup) {

    var data_s[] int
    for len(data) >= 30 {
        data_s, data = Partition(data)
        if len(data_s) > 1000 &&
                runtime.NumGoroutine() < runtime.NumCPU() * 8 {
            wg.Add(1)
            go func(d[] int) {
                QuSort(d, wg)
                wg.Done()
            }(data_s)
        } else {
            QuSort(data_s, wg)
        }
    }
    InsertSort(data)
}

func QSort(data[] int) {

    var wg sync.WaitGroup
    QuSort(data, &wg)
    wg.Wait()
}
.
.
.

Sorting 50 million numbers with Goroutines ...
Time: 0.95s

Go is a language that makes threads comparatively easy to use. Go is a well-designed language and by checking the array boundaries it is also very secure and yet quite fast.

A Multi‑Threaded Branchless Quicksort in C

easylang.online - easy programming online