Sorting and Searching in Go

Sorting and searching are fundamental operations in programming. Go’s sort package provides efficient implementations of common sorting algorithms and utilities for searching. This guide covers everything you need to know about sorting and searching in Go.

Basic Sorting

Sorting Built-in Types

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Sort integers
	ints := []int{3, 1, 4, 1, 5, 9, 2, 6}
	sort.Ints(ints)
	fmt.Println("Sorted ints:", ints)

	// Sort strings
	strings := []string{"banana", "apple", "cherry", "date"}
	sort.Strings(strings)
	fmt.Println("Sorted strings:", strings)

	// Sort floats
	floats := []float64{3.14, 2.71, 1.41, 1.73}
	sort.Float64s(floats)
	fmt.Println("Sorted floats:", floats)

	// Check if already sorted
	fmt.Println("Is sorted:", sort.IntsAreSorted(ints))
}

Reverse Sorting

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Reverse sort integers
	ints := []int{3, 1, 4, 1, 5, 9, 2, 6}
	sort.Sort(sort.Reverse(sort.IntSlice(ints)))
	fmt.Println("Reverse sorted ints:", ints)

	// Reverse sort strings
	strings := []string{"banana", "apple", "cherry", "date"}
	sort.Sort(sort.Reverse(sort.StringSlice(strings)))
	fmt.Println("Reverse sorted strings:", strings)

	// Reverse sort floats
	floats := []float64{3.14, 2.71, 1.41, 1.73}
	sort.Sort(sort.Reverse(sort.Float64Slice(floats)))
	fmt.Println("Reverse sorted floats:", floats)
}

Custom Sorting

Implementing the Sort Interface

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

// Implement sort.Interface
type PersonSlice []Person

func (p PersonSlice) Len() int           { return len(p) }
func (p PersonSlice) Less(i, j int) bool { return p[i].Age < p[j].Age }
func (p PersonSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func main() {
	people := PersonSlice{
		{"Alice", 30},
		{"Bob", 25},
		{"Charlie", 35},
		{"Diana", 28},
	}

	sort.Sort(people)
	fmt.Println("Sorted by age:")
	for _, p := range people {
		fmt.Printf("%s: %d\n", p.Name, p.Age)
	}
}

Using sort.Slice

package main

import (
	"fmt"
	"sort"
)

type Product struct {
	Name  string
	Price float64
	Stock int
}

func main() {
	products := []Product{
		{"Laptop", 999.99, 5},
		{"Mouse", 29.99, 50},
		{"Keyboard", 79.99, 30},
		{"Monitor", 299.99, 10},
	}

	// Sort by price
	sort.Slice(products, func(i, j int) bool {
		return products[i].Price < products[j].Price
	})

	fmt.Println("Sorted by price:")
	for _, p := range products {
		fmt.Printf("%s: $%.2f\n", p.Name, p.Price)
	}

	// Sort by stock (descending)
	sort.Slice(products, func(i, j int) bool {
		return products[i].Stock > products[j].Stock
	})

	fmt.Println("\nSorted by stock (descending):")
	for _, p := range products {
		fmt.Printf("%s: %d units\n", p.Name, p.Stock)
	}
}

Multi-Key Sorting

package main

import (
	"fmt"
	"sort"
)

type Student struct {
	Name  string
	Grade int
	Score float64
}

func main() {
	students := []Student{
		{"Alice", 10, 95.5},
		{"Bob", 10, 87.3},
		{"Charlie", 9, 92.1},
		{"Diana", 10, 95.5},
		{"Eve", 9, 88.7},
	}

	// Sort by grade (ascending), then by score (descending)
	sort.Slice(students, func(i, j int) bool {
		if students[i].Grade != students[j].Grade {
			return students[i].Grade < students[j].Grade
		}
		return students[i].Score > students[j].Score
	})

	fmt.Println("Sorted by grade, then score:")
	for _, s := range students {
		fmt.Printf("%s: Grade %d, Score %.1f\n", s.Name, s.Grade, s.Score)
	}
}

Searching

Binary Search

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Binary search requires sorted slice
	numbers := []int{1, 3, 5, 7, 9, 11, 13, 15}

	// Search for value
	target := 7
	index := sort.SearchInts(numbers, target)

	if index < len(numbers) && numbers[index] == target {
		fmt.Printf("Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("%d not found\n", target)
	}

	// Search for insertion point
	target = 8
	index = sort.SearchInts(numbers, target)
	fmt.Printf("Insert %d at index %d\n", target, index)
}

Custom Binary Search

package main

import (
	"fmt"
	"sort"
)

type Book struct {
	Title string
	Year  int
}

func main() {
	books := []Book{
		{"Go Programming", 2015},
		{"The Go Way", 2016},
		{"Advanced Go", 2018},
		{"Go Concurrency", 2019},
		{"Go Systems", 2020},
	}

	// Search using sort.Search
	target := 2018
	index := sort.Search(len(books), func(i int) bool {
		return books[i].Year >= target
	})

	if index < len(books) && books[index].Year == target {
		fmt.Printf("Found: %s (%d)\n", books[index].Title, books[index].Year)
	} else {
		fmt.Printf("Year %d not found\n", target)
	}
}

Linear Search

package main

import (
	"fmt"
)

func linearSearch(arr []int, target int) int {
	for i, v := range arr {
		if v == target {
			return i
		}
	}
	return -1
}

func main() {
	numbers := []int{3, 1, 4, 1, 5, 9, 2, 6}

	target := 5
	index := linearSearch(numbers, target)

	if index != -1 {
		fmt.Printf("Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("%d not found\n", target)
	}
}

Advanced Sorting Techniques

Stable Sorting

package main

import (
	"fmt"
	"sort"
)

type Record struct {
	ID    int
	Value string
}

func main() {
	records := []Record{
		{1, "A"},
		{2, "B"},
		{3, "A"},
		{4, "C"},
		{5, "B"},
	}

	// Stable sort preserves original order for equal elements
	sort.SliceStable(records, func(i, j int) bool {
		return records[i].Value < records[j].Value
	})

	fmt.Println("Stable sorted:")
	for _, r := range records {
		fmt.Printf("ID: %d, Value: %s\n", r.ID, r.Value)
	}
}

Partial Sorting

package main

import (
	"fmt"
	"sort"
)

func main() {
	numbers := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}

	// Find top 3 elements
	sort.Slice(numbers, func(i, j int) bool {
		return numbers[i] > numbers[j]
	})

	fmt.Println("Top 3 elements:", numbers[:3])

	// Find bottom 3 elements
	sort.Slice(numbers, func(i, j int) bool {
		return numbers[i] < numbers[j]
	})

	fmt.Println("Bottom 3 elements:", numbers[:3])
}

Sorting with Custom Comparator

package main

import (
	"fmt"
	"sort"
	"strings"
)

type File struct {
	Name string
	Size int64
}

func main() {
	files := []File{
		{"document.pdf", 1024000},
		{"image.jpg", 2048000},
		{"archive.zip", 5120000},
		{"readme.txt", 2048},
	}

	// Sort by size (descending)
	sort.Slice(files, func(i, j int) bool {
		return files[i].Size > files[j].Size
	})

	fmt.Println("Sorted by size (descending):")
	for _, f := range files {
		fmt.Printf("%s: %.2f MB\n", f.Name, float64(f.Size)/1024/1024)
	}

	// Sort by name (case-insensitive)
	sort.Slice(files, func(i, j int) bool {
		return strings.ToLower(files[i].Name) < strings.ToLower(files[j].Name)
	})

	fmt.Println("\nSorted by name:")
	for _, f := range files {
		fmt.Println(f.Name)
	}
}

Practical Examples

Finding Duplicates

package main

import (
	"fmt"
	"sort"
)

func findDuplicates(arr []int) []int {
	if len(arr) == 0 {
		return []int{}
	}

	sort.Ints(arr)
	var duplicates []int

	for i := 0; i < len(arr)-1; i++ {
		if arr[i] == arr[i+1] && (len(duplicates) == 0 || duplicates[len(duplicates)-1] != arr[i]) {
			duplicates = append(duplicates, arr[i])
		}
	}

	return duplicates
}

func main() {
	numbers := []int{1, 2, 2, 3, 3, 3, 4, 5, 5}
	fmt.Println("Duplicates:", findDuplicates(numbers))
}

Merging Sorted Arrays

package main

import (
	"fmt"
	"sort"
)

func mergeSorted(arr1, arr2 []int) []int {
	result := make([]int, len(arr1)+len(arr2))
	copy(result, arr1)
	copy(result[len(arr1):], arr2)
	sort.Ints(result)
	return result
}

func main() {
	arr1 := []int{1, 3, 5, 7}
	arr2 := []int{2, 4, 6, 8}
	merged := mergeSorted(arr1, arr2)
	fmt.Println("Merged:", merged)
}

Finding Median

package main

import (
	"fmt"
	"sort"
)

func findMedian(arr []int) float64 {
	if len(arr) == 0 {
		return 0
	}

	sorted := make([]int, len(arr))
	copy(sorted, arr)
	sort.Ints(sorted)

	n := len(sorted)
	if n%2 == 1 {
		return float64(sorted[n/2])
	}
	return float64(sorted[n/2-1]+sorted[n/2]) / 2
}

func main() {
	numbers := []int{3, 1, 4, 1, 5, 9, 2, 6}
	fmt.Printf("Median: %.1f\n", findMedian(numbers))
}

Performance Considerations

Sorting Performance

package main

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

func main() {
	// Generate random data
	sizes := []int{1000, 10000, 100000}

	for _, size := range sizes {
		data := make([]int, size)
		for i := 0; i < size; i++ {
			data[i] = rand.Intn(10000)
		}

		start := time.Now()
		sort.Ints(data)
		elapsed := time.Since(start)

		fmt.Printf("Sorting %d elements: %v\n", size, elapsed)
	}
}

Best Practices

✅ Good Practices

// Use sort.Slice for simple cases
sort.Slice(items, func(i, j int) bool {
	return items[i].Priority > items[j].Priority
})

// Use sort.SliceStable when order matters
sort.SliceStable(items, func(i, j int) bool {
	return items[i].Date.Before(items[j].Date)
})

// Ensure slice is sorted before binary search
sort.Ints(numbers)
index := sort.SearchInts(numbers, target)

// Use appropriate search for your data
if sort.SearchIntsAreSorted(numbers, target) {
	// Found
}

❌ Anti-Patterns

// Don't use binary search on unsorted data
index := sort.SearchInts(unsorted, target) // Wrong!

// Don't repeatedly sort the same data
for i := 0; i < 1000; i++ {
	sort.Ints(data) // Inefficient
}

// Don't ignore sort stability when needed
sort.Slice(items, func(i, j int) bool {
	return items[i].Date < items[j].Date
}) // May lose original order

Resources

Summary

Go’s sort package provides efficient and flexible sorting and searching capabilities:

Use built-in functions for standard types
Implement sort.Interface for custom types
Use sort.Slice for simple custom sorting
Use binary search for sorted data
Consider stability when needed
Profile performance for large datasets

With these tools, you can efficiently sort and search data in your Go applications.