Comparison Based vs Non Comparison Based Sorting in DSA Go - Trade-offs & Analysis

Mental Model

Sorting can be done by comparing elements or by using their values directly without comparisons.

Analogy: Imagine sorting books by comparing their titles one by one (comparison based) versus sorting mail by zip codes using bins (non comparison based).

Array: [4, 2, 7, 1, 3]
Comparison Based: compare pairs -> swap -> sorted
Non Comparison Based: use value buckets -> collect -> sorted

Dry Run Walkthrough

Input: list: [4, 2, 7, 1, 3]

Goal: Show how comparison based and non comparison based sorting handle the same list differently

Step 1: Comparison based: compare 4 and 2, swap because 4 > 2

[2, 4, 7, 1, 3]

Why: We need to order elements by comparing pairs

Step 2: Comparison based: compare 4 and 7, no swap because 4 < 7

[2, 4, 7, 1, 3]

Why: Keep larger elements towards the end

Step 3: Comparison based: compare 7 and 1, swap because 7 > 1

[2, 4, 1, 7, 3]

Why: Smaller elements move forward

Step 4: Non comparison based: create buckets for values 1 to 7

Buckets: 1:[1], 2:[2], 3:[3], 4:[4], 7:[7]

Why: Use values as direct indices to buckets

Step 5: Non comparison based: collect elements from buckets in order

[1, 2, 3, 4, 7]

Why: Collecting buckets in order gives sorted list

Result:

Comparison based final: [1, 2, 3, 4, 7]
Non comparison based final: [1, 2, 3, 4, 7]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// Comparison based sorting: Bubble Sort
func bubbleSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j] // swap
			}
		}
	}
}

// Non comparison based sorting: Counting Sort (for positive integers)
func countingSort(arr []int) []int {
	max := 0
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	count := make([]int, max+1)
	for _, v := range arr {
		count[v]++ // count occurrences
	}
	sorted := []int{}
	for i, c := range count {
		for c > 0 {
			sorted = append(sorted, i) // add i c times
			c--
		}
	}
	return sorted
}

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

	// Comparison based
	bubbleSort(arr)
	fmt.Println("Comparison based sorted:", arr)

	// Non comparison based
	arr2 := []int{4, 2, 7, 1, 3}
	sorted := countingSort(arr2)
	fmt.Println("Non comparison based sorted:", sorted)
}

if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j]

compare adjacent elements and swap if out of order

count[v]++

count occurrences of each value

for i, c := range count { for c > 0 { sorted = append(sorted, i) c-- }

collect values from count array in order to build sorted list

Output

Original: [4 2 7 1 3]

Comparison based sorted: [1 2 3 4 7]

Non comparison based sorted: [1 2 3 4 7]

Complexity Analysis

Time: O(n^2) for comparison based bubble sort because it compares pairs repeatedly; O(n + k) for counting sort where k is max value, because it counts and collects

Space: O(1) extra space for bubble sort; O(k) extra space for counting sort due to count array

vs Alternative: Comparison based sorts work on any data but can be slower; non comparison based sorts are faster but need value constraints (like integers in a range)

Edge Cases

empty list

both sorts return empty list without error

DSA Go

for i := 0; i < len(arr)-1; i++ {

list with duplicates

both sorts correctly handle duplicates preserving count

DSA Go

count[v]++

list with single element

both sorts return the same single element list

DSA Go

for i := 0; i < len(arr)-1; i++ {

When to Use This Pattern

When sorting integers or data with limited range, consider non comparison based sorting for faster performance; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on negative or non-integer data without adjustments
Fix: Ensure data fits counting sort constraints or use comparison based sorting

Mistake: Assuming comparison based sorts are always slower without considering data size
Fix: Understand that for small or nearly sorted data, comparison based sorts can be efficient

Summary

Comparison based sorting uses element comparisons to order data; non comparison based sorting uses data values directly.

Use comparison based sorting for general data and non comparison based sorting for integers with limited range.

The key insight is that non comparison based sorting can be faster by avoiding comparisons but requires specific data conditions.