Sorting is one of the most common tasks in programming, and learning different sorting algorithms helps build your understanding of how data structures and algorithms work together. One of the most powerful and widely used sorting techniques is Quick Sort. It’s known for being fast and efficient, especially when dealing with large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Quick Sort follows a clever approach known as divide and conquer. It works by selecting a pivot element, arranging the array so that all elements smaller than the pivot come before it, and all elements greater come after. This process continues recursively until the entire array is sorted. Because of its speed and efficiency, Quick Sort is often used in libraries, frameworks, and performance-critical systems. Learning how to implement it in GoLang gives you deeper insight into how real-world sorting works behind the scenes.
Program 1: Quick Sort Using Recursion
Let’s start with the most common way to implement Quick Sort — using recursion. This method is simple to understand and shows how divide and conquer works in action.
package main
import "fmt"
func quickSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
right := []int{}
for i, v := range arr {
if i == len(arr)/2 {
continue
}
if v <= pivot {
left = append(left, v)
} else {
right = append(right, v)
}
}
sorted := append(quickSort(left), pivot)
sorted = append(sorted, quickSort(right)...)
return sorted
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
sorted := quickSort(numbers)
fmt.Println("Sorted array:", sorted)
}This program uses a pivot (the middle element in this case) and divides the array into two slices — one for values less than or equal to the pivot, and one for greater values. It recursively sorts both slices and merges them together. This version of Quick Sort is very beginner-friendly, as it clearly shows the main concept without worrying about complex optimizations.
Program 2: Quick Sort with In-Place Partitioning
While the first version creates new slices, this one performs sorting in-place, meaning it rearranges elements directly in the original array. This approach uses less memory and is closer to how Quick Sort is implemented in real-world systems.
package main
import "fmt"
func partition(arr []int, low, high int) int {
pivot := arr[high]
i := low - 1
for j := low; j < high; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
}
func quickSortInPlace(arr []int, low, high int) {
if low < high {
pi := partition(arr, low, high)
quickSortInPlace(arr, low, pi-1)
quickSortInPlace(arr, pi+1, high)
}
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
quickSortInPlace(numbers, 0, len(numbers)-1)
fmt.Println("Sorted array (in-place):", numbers)
}In this version, we use the Lomuto partition scheme. The pivot is placed in its correct position, and all smaller elements are moved to its left while larger ones go to its right. It’s memory-efficient and shows how the algorithm manipulates indexes directly. Beginners can practice stepping through this code to understand how data swaps take place.
Program 3: Quick Sort in Descending Order
Sometimes you may need to sort data in descending order instead of ascending. In Quick Sort, this change is simple — you just reverse the comparison in the partition step.
package main
import "fmt"
func partitionDesc(arr []int, low, high int) int {
pivot := arr[high]
i := low - 1
for j := low; j < high; j++ {
if arr[j] > pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
}
func quickSortDesc(arr []int, low, high int) {
if low < high {
pi := partitionDesc(arr, low, high)
quickSortDesc(arr, low, pi-1)
quickSortDesc(arr, pi+1, high)
}
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
quickSortDesc(numbers, 0, len(numbers)-1)
fmt.Println("Sorted array (descending):", numbers)
}This program uses the same logic as before but reverses the comparison so that larger values come first. It’s a great exercise to show how small changes in comparison logic can completely change the sorting order.
Program 4: Quick Sort Using Random Pivot Selection
Choosing a good pivot is crucial in Quick Sort because it affects performance. In this version, we choose a random pivot to avoid worst-case scenarios that can happen if the array is already sorted.
package main
import (
"fmt"
"math/rand"
"time"
)
func partitionRandom(arr []int, low, high int) int {
rand.Seed(time.Now().UnixNano())
pivotIndex := rand.Intn(high-low+1) + low
arr[pivotIndex], arr[high] = arr[high], arr[pivotIndex]
pivot := arr[high]
i := low - 1
for j := low; j < high; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
}
func quickSortRandom(arr []int, low, high int) {
if low < high {
pi := partitionRandom(arr, low, high)
quickSortRandom(arr, low, pi-1)
quickSortRandom(arr, pi+1, high)
}
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
quickSortRandom(numbers, 0, len(numbers)-1)
fmt.Println("Sorted array (random pivot):", numbers)
}Here, each time we sort, a random pivot is selected. This reduces the chances of running into the worst-case time complexity, making Quick Sort more reliable. Beginners can see how adding just a few lines can improve algorithm efficiency.
Program 5: Quick Sort Using Generics (Go 1.18+)
With Go’s introduction of generics, you can now write sorting algorithms that work with any data type — integers, floats, or even strings. This final version shows how to use generics to make Quick Sort flexible and reusable.
package main
import "fmt"
func quickSortGeneric[T comparable](arr []T, less func(a, b T) bool) []T {
if len(arr) < 2 {
return arr
}
pivot := arr[len(arr)/2]
left := []T{}
right := []T{}
for i, v := range arr {
if i == len(arr)/2 {
continue
}
if less(v, pivot) {
left = append(left, v)
} else {
right = append(right, v)
}
}
sorted := append(quickSortGeneric(left, less), pivot)
sorted = append(sorted, quickSortGeneric(right, less)...)
return sorted
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
sortedInts := quickSortGeneric(numbers, func(a, b int) bool { return a < b })
fmt.Println("Sorted integers:", sortedInts)
names := []string{"Hermione", "Ron", "Harry", "Draco", "Luna"}
sortedNames := quickSortGeneric(names, func(a, b string) bool { return a < b })
fmt.Println("Sorted names:", sortedNames)
}This version uses Go’s generics feature, making the same function work for multiple types. Beginners get to see how powerful and flexible Go has become with the addition of generics. It’s an excellent example of writing clean, reusable code.
Frequently Asked Questions (FAQ)
Understanding Quick Sort can raise a few common questions, especially for beginners. Let’s clear them up.
Q1: What is Quick Sort used for?
Quick Sort is used to arrange data efficiently. It’s especially useful in large datasets and real-time systems due to its fast average performance.
Q2: How does Quick Sort differ from Merge Sort?
Quick Sort sorts data in-place and uses less memory, while Merge Sort needs extra space for merging. However, Merge Sort is stable and works well for linked lists.
Q3: What is the time complexity of Quick Sort?
The average time complexity is O(n log n), but in the worst case (like sorted data with a bad pivot), it can degrade to O(n²).
Q4: What does the pivot mean in Quick Sort?
A pivot is an element chosen from the array that helps divide data into smaller parts — one with elements smaller than it and one with elements larger than it.
Q5: Is Quick Sort stable?
No, Quick Sort is not stable because it may change the relative order of equal elements. But it’s one of the fastest comparison-based sorting algorithms.
Conclusion
Quick Sort is a brilliant example of how divide-and-conquer strategies can solve problems efficiently. Its speed, simplicity, and wide application make it one of the most popular sorting algorithms in the programming world. By learning to implement Quick Sort in GoLang — from recursive to in-place and even generic versions — you not only strengthen your understanding of sorting but also get hands-on experience with core Go features.
Keep experimenting with different pivot choices, data types, and variations. Every time you tweak and run the code, you’ll uncover a deeper understanding of how sorting really works under the hood. With consistent practice, algorithms like Quick Sort will soon feel as natural as writing a loop.
