Complete Guide to Sorting Algorithms

Complete Guide to Sorting Algorithms

Sorting algorithms are fundamental to computer science and essential for technical interviews. This guide covers all major sorting techniques with concise explanations, Go implementations, and practical analysis.

Overview of Sorting Algorithms

What is Sorting? Arranging elements in a specific order (ascending or descending).

Key Considerations:

Time Complexity: How fast is the algorithm?
Space Complexity: How much extra memory is needed?
Stability: Does it preserve relative order of equal elements?
In-place: Does it sort without extra space?

1. Bubble Sort

� Definition

Bubble Sort repeatedly compares adjacent elements and swaps them if they're in wrong order. Larger elements "bubble up" to the end.

Algorithm Steps

Compare adjacent elements from start
Swap if left > right (for ascending order)
Continue until end of array
Repeat for n-1 passes

Implementation

package main

import "fmt"

func BubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // Flag to optimize - if no swaps, array is sorted
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j] // Swap
                swapped = true
            }
        }
        // If no swaps occurred, array is sorted
        if !swapped {
            break
        }
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Original:", arr)
    BubbleSort(arr)
    fmt.Println("Sorted:", arr)
}

Dry Run Example

Array: [5, 2, 8, 1]

Pass 1: [5,2,8,1] → [2,5,8,1] → [2,5,8,1] → [2,5,1,8]
Pass 2: [2,5,1,8] → [2,5,1,8] → [2,1,5,8]
Pass 3: [2,1,5,8] → [1,2,5,8]
Result: [1,2,5,8]

Complexity

Time: Best O(n), Average/Worst O(n²)
Space: O(1)
Stable: Yes
In-place: Yes

When to Use

✅ Use When: Educational purposes, very small datasets
❌ Avoid When: Large datasets, performance matters

2. Selection Sort

🎯 Definition

Selection Sort finds the minimum element and places it at the beginning. Repeat for remaining unsorted portion.

Algorithm Steps

Find minimum element in unsorted array
Swap it with first element
Move boundary of unsorted array
Repeat until array is sorted

Implementation

package main

import "fmt"

func SelectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // Find minimum element index
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        // Swap minimum element with first element
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

func main() {
    arr := []int{64, 25, 12, 22, 11}
    fmt.Println("Original:", arr)
    SelectionSort(arr)
    fmt.Println("Sorted:", arr)
}

Dry Run Example

Array: [5, 2, 8, 1]

Pass 1: Find min(5,2,8,1)=1, swap: [1,2,8,5]
Pass 2: Find min(2,8,5)=2, no swap: [1,2,8,5]
Pass 3: Find min(8,5)=5, swap: [1,2,5,8]
Result: [1,2,5,8]

Complexity

Time: O(n²) for all cases
Space: O(1)
Stable: No
In-place: Yes

When to Use

✅ Use When: Memory is limited, small datasets
❌ Avoid When: Large datasets, stability required

3. Insertion Sort

📝 Definition

Insertion Sort builds sorted array one element at a time by inserting each element into its correct position.

Algorithm Steps

Start from second element (assume first is sorted)
Compare current element with previous elements
Shift larger elements to right
Insert current element at correct position

Implementation

package main

import "fmt"

func InsertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        
        // Move elements greater than key to one position ahead
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 4, 6, 1, 3}
    fmt.Println("Original:", arr)
    InsertionSort(arr)
    fmt.Println("Sorted:", arr)
}

Dry Run Example

Array: [5, 2, 8, 1]

i=1: key=2, shift 5: [2,5,8,1]
i=2: key=8, no shift: [2,5,8,1]
i=3: key=1, shift 8,5,2: [1,2,5,8]
Result: [1,2,5,8]

Complexity

Time: Best O(n), Average/Worst O(n²)
Space: O(1)
Stable: Yes
In-place: Yes

When to Use

✅ Use When: Small datasets, nearly sorted data, online algorithm needed
❌ Avoid When: Large datasets with random order

4. Merge Sort

� Definition

Merge Sort uses divide-and-conquer: divide array into halves, sort them recursively, then merge sorted halves.

Algorithm Steps

Divide array into two halves
Recursively sort both halves
Merge the sorted halves
Base case: arrays with 1 element are sorted

Implementation

package main

import "fmt"

func MergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    mid := len(arr) / 2
    left := MergeSort(arr[:mid])
    right := MergeSort(arr[mid:])
    
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    // Merge while both arrays have elements
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    
    // Append remaining elements
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    
    return result
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    fmt.Println("Original:", arr)
    sorted := MergeSort(arr)
    fmt.Println("Sorted:", sorted)
}

Dry Run Example

Array: [4, 2, 7, 1]

Divide: [4,2,7,1] → [4,2] & [7,1]
Further: [4] & [2], [7] & [1]
Merge: [2,4] & [1,7]
Final merge: [1,2,4,7]

Complexity

Time: O(n log n) for all cases
Space: O(n)
Stable: Yes
In-place: No

When to Use

✅ Use When: Large datasets, stability required, guaranteed O(n log n)
❌ Avoid When: Memory is very limited

5. Quick Sort

⚡ Definition

Quick Sort picks a pivot, partitions array around it, then recursively sorts partitions.

Algorithm Steps

Choose a pivot element
Partition: elements < pivot on left, > pivot on right
Recursively sort left and right partitions
Combine results

Implementation

package main

import "fmt"

func QuickSort(arr []int, low, high int) {
    if low < high {
        // Partition and get pivot index
        pi := partition(arr, low, high)
        
        // Recursively sort elements before and after partition
        QuickSort(arr, low, pi-1)
        QuickSort(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high] // Choose last element as pivot
    i := low - 1       // Index of smaller element
    
    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 main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    fmt.Println("Original:", arr)
    QuickSort(arr, 0, len(arr)-1)
    fmt.Println("Sorted:", arr)
}

Dry Run Example

Array: [4, 2, 7, 1], Pivot: 1

Partition: [1] | [4,2,7] (pivot at index 0)
Right partition: [4,2,7], Pivot: 7
Result: [1] | [2,4] | [7]
Final: [1,2,4,7]

Complexity

Time: Best/Average O(n log n), Worst O(n²)
Space: O(log n) average, O(n) worst
Stable: No
In-place: Yes

When to Use

✅ Use When: Average case performance matters, in-place sorting needed
❌ Avoid When: Worst-case guarantee required

6. Counting Sort

� Definition

Counting Sort counts occurrences of each element, then reconstructs sorted array. Works only with integers in known range.

Algorithm Steps

Find maximum element to determine range
Create count array for range [0...max]
Count occurrences of each element
Transform counts to actual positions
Build sorted array using positions

Implementation

package main

import "fmt"

func CountingSort(arr []int) []int {
    if len(arr) == 0 {
        return arr
    }
    
    // Find maximum element
    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }
    
    // Count occurrences
    count := make([]int, max+1)
    for _, v := range arr {
        count[v]++
    }
    
    // Transform counts to positions
    for i := 1; i <= max; i++ {
        count[i] += count[i-1]
    }
    
    // Build result array
    result := make([]int, len(arr))
    for i := len(arr) - 1; i >= 0; i-- {
        result[count[arr[i]]-1] = arr[i]
        count[arr[i]]--
    }
    
    return result
}

func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    fmt.Println("Original:", arr)
    sorted := CountingSort(arr)
    fmt.Println("Sorted:", sorted)
}

Dry Run Example

Array: [4, 2, 2, 1], Max: 4

Count: [0,1,2,0,1] (counts for 0,1,2,3,4)
Positions: [0,1,3,3,4]
Build: Place elements using positions
Result: [1,2,2,4]

Complexity

Time: O(n + k) where k is range
Space: O(k)
Stable: Yes
In-place: No

When to Use

✅ Use When: Small range of integers, need stability
❌ Avoid When: Large range, floating-point numbers

7. Bucket Sort

🪣 Definition

Bucket Sort distributes elements into buckets, sorts each bucket individually, then concatenates results.

Algorithm Steps

Create empty buckets
Distribute elements into buckets based on range
Sort each bucket individually
Concatenate all bucket contents

Implementation

package main

import (
    "fmt"
    "sort"
)

func BucketSort(arr []float64, numBuckets int) []float64 {
    if len(arr) == 0 {
        return arr
    }
    
    // Find min and max values
    min, max := arr[0], arr[0]
    for _, v := range arr {
        if v < min {
            min = v
        }
        if v > max {
            max = v
        }
    }
    
    // Create buckets
    buckets := make([][]float64, numBuckets)
    for i := range buckets {
        buckets[i] = make([]float64, 0)
    }
    
    // Distribute elements into buckets
    bucketRange := (max - min) / float64(numBuckets)
    for _, v := range arr {
        bucketIndex := int((v - min) / bucketRange)
        if bucketIndex >= numBuckets {
            bucketIndex = numBuckets - 1
        }
        buckets[bucketIndex] = append(buckets[bucketIndex], v)
    }
    
    // Sort each bucket and concatenate
    result := make([]float64, 0, len(arr))
    for _, bucket := range buckets {
        sort.Float64s(bucket)
        result = append(result, bucket...)
    }
    
    return result
}

func main() {
    arr := []float64{0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}
    fmt.Println("Original:", arr)
    sorted := BucketSort(arr, 3)
    fmt.Println("Sorted:", sorted)
}

Dry Run Example

Array: [0.42, 0.32, 0.33, 0.52], Buckets: 2

Range: [0-0.5], [0.5-1.0]
Bucket 0: [0.42, 0.32, 0.33] → [0.32, 0.33, 0.42]
Bucket 1: [0.52] → [0.52]
Result: [0.32, 0.33, 0.42, 0.52]

Complexity

Time: Average O(n + k), Worst O(n²)
Space: O(n + k)
Stable: Yes (if stable sort used for buckets)
In-place: No

When to Use

✅ Use When: Uniformly distributed data, floating-point numbers
❌ Avoid When: Non-uniform distribution, limited memory

Algorithm Comparison Summary

Algorithm	Time Complexity	Space	Stable	In-place	Best Use Case
Bubble Sort	O(n²)	O(1)	✅	✅	Educational, tiny datasets
Selection Sort	O(n²)	O(1)	❌	✅	Memory limited, small data
Insertion Sort	O(n²)	O(1)	✅	✅	Small/nearly sorted data
Merge Sort	O(n log n)	O(n)	✅	❌	Large datasets, stability needed
Quick Sort	O(n log n)*	O(log n)	❌	✅	General purpose, average case
Counting Sort	O(n + k)	O(k)	✅	❌	Small integer range
Bucket Sort	O(n + k)	O(n)	✅	❌	Uniform distribution

*Average case, worst case O(n²)

When to Use Which Algorithm?

Decision Tree

Data size?
├── Small (< 50) → Insertion Sort
├── Medium (50-10k) → Quick Sort
└── Large (> 10k) → 
    ├── Stability needed? → Merge Sort
    ├── Integer range small? → Counting Sort
    ├── Uniform distribution? → Bucket Sort
    └── Default → Quick Sort

Interview Tips

Common Questions:

Q: Why is Quick Sort preferred over Merge Sort?
A: In-place sorting, better cache performance, average O(n log n)
Q: When would you choose Insertion Sort?
A: Small datasets, nearly sorted data, online algorithms
Q: Explain stability in sorting
A: Stable sorts preserve relative order of equal elements
Q: Which sort for real-time systems?
A: Merge Sort (guaranteed O(n log n)) or Heap Sort

Key Points to Remember:

Understand trade-offs: Time vs Space vs Stability
Know when each algorithm shines
Practice dry runs for better understanding
Consider real-world constraints (memory, stability, etc.)

Practice Problems

Easy:

Implement bubble sort with optimization
Sort array using selection sort
Insertion sort for linked list

Medium:
4. Merge k sorted arrays 5. Quick sort with random pivot 6. Sort colors (Dutch flag problem)

Hard: 7. External sorting for large files 8. Sort array with 3 different elements 9. Implement hybrid sort (Intro sort)

Real-World Applications

Databases: Query optimization, indexing
Operating Systems: Process scheduling, memory management
Graphics: Z-buffer sorting, polygon rendering
Search Engines: PageRank sorting, relevance scoring
Machine Learning: Data preprocessing, feature selection

Conclusion

Understanding sorting algorithms is crucial for:

Technical interviews: Common questions and problem-solving
Algorithm design: Choosing right approach for constraints
Performance optimization: Time/space trade-offs
System design: Large-scale data processing

Key Takeaways:

No single best algorithm - depends on constraints
Understand trade-offs between time, space, and stability
Practice implementations and dry runs
Know when to use each algorithm in real scenarios

Master these fundamentals to excel in technical interviews and build efficient systems!