Go Sorting Algorithms Benchmark

Bubble Sort

This benchmark uses the Bubble Sort algorithm to sort the array. Bubble Sort works by repeatedly swapping the adjacent elements, if they are in the wrong order.

Comparison

• Bubble Sort sort is 738.20% slower than Builtin Sort sort.
• Bubble Sort sort is 236.16% slower than Insertion Sort sort.
• Bubble Sort sort is 292.95% slower than Merge Sort sort.
• Bubble Sort sort is 978.88% slower than Quick Sort sort.
• Bubble Sort sort is 55.05% slower than Selection Sort sort.

type BubbleSort struct{}

func (s *BubbleSort) sort(data []int) {
	n := len(data)
	for i := 0; i < n; i++ {
		for j := 0; j < n-i-1; j++ {
			if data[j] > data[j+1] {
				data[j], data[j+1] = data[j+1], data[j]
			}
		}
	}
}

func BenchmarkBubbleSort_sort(b *testing.B) {
	var s BubbleSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Bubble Sort sort

By Run Count

By CPU Core Count

Builtin Sort

This benchmark uses the built-in sort package to sort the array.

Comparison

• Builtin Sort sort is 88.07% faster than Bubble Sort sort.
• Builtin Sort sort is 59.90% faster than Insertion Sort sort.
• Builtin Sort sort is 53.12% faster than Merge Sort sort.
• Builtin Sort sort is 28.71% slower than Quick Sort sort.
• Builtin Sort sort is 81.50% faster than Selection Sort sort.

type BuiltinSort struct{}

func (s *BuiltinSort) sort(data []int) {
	sort.Ints(data)
}

func BenchmarkBuiltinSort_sort(b *testing.B) {
	var s BuiltinSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Builtin Sort sort

By Run Count

By CPU Core Count

Insertion Sort

This benchmark uses the Insertion Sort algorithm to sort the array. Insertion Sort works by repeatedly inserting the next element into the sorted part of the array.

Comparison

• Insertion Sort sort is 70.25% faster than Bubble Sort sort.
• Insertion Sort sort is 149.35% slower than Builtin Sort sort.
• Insertion Sort sort is 16.90% slower than Merge Sort sort.
• Insertion Sort sort is 220.94% slower than Quick Sort sort.
• Insertion Sort sort is 53.88% faster than Selection Sort sort.

type InsertionSort struct{}

func (s *InsertionSort) sort(data []int) {
	for i := 1; i < len(data); i++ {
		key := data[i]
		j := i - 1

		for j >= 0 && data[j] > key {
			data[j+1] = data[j]
			j--
		}
		data[j+1] = key
	}
}

func BenchmarkInsertionSort_sort(b *testing.B) {
	var s InsertionSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Insertion Sort sort

By Run Count

By CPU Core Count

Merge Sort

This benchmark uses the Merge Sort algorithm to sort the array. Merge Sort works by repeatedly splitting the array into two halves, sorting them and then merging them back together.

Comparison

• Merge Sort sort is 74.55% faster than Bubble Sort sort.
• Merge Sort sort is 113.31% slower than Builtin Sort sort.
• Merge Sort sort is 14.45% faster than Insertion Sort sort.
• Merge Sort sort is 174.56% slower than Quick Sort sort.
• Merge Sort sort is 60.54% faster than Selection Sort sort.

type MergeSort struct{}

func (s *MergeSort) sort(data []int) []int {
	if len(data) <= 1 {
		return data
	}

	// Divide the array in half
	middle := len(data) / 2
	left := s.sort(data[:middle])
	right := s.sort(data[middle:])

	return s.merge(left, right)
}

func (s *MergeSort) merge(left, right []int) []int {
	var result []int
	leftIndex, rightIndex := 0, 0

	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] < right[rightIndex] {
			result = append(result, left[leftIndex])
			leftIndex++
		} else {
			result = append(result, right[rightIndex])
			rightIndex++
		}
	}

	// Append any remaining elements
	result = append(result, left[leftIndex:]...)
	result = append(result, right[rightIndex:]...)

	return result
}

func BenchmarkMergeSort_sort(b *testing.B) {
	var s MergeSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Merge Sort sort

By Run Count

By CPU Core Count

Quick Sort

This benchmark uses the Quick Sort algorithm to sort the array. Quick Sort works by repeatedly selecting a pivot element, partitioning the array around the pivot and then sorting the two partitions.

Comparison

• Quick Sort sort is 90.73% faster than Bubble Sort sort.
• Quick Sort sort is 22.31% faster than Builtin Sort sort.
• Quick Sort sort is 68.84% faster than Insertion Sort sort.
• Quick Sort sort is 63.58% faster than Merge Sort sort.
• Quick Sort sort is 85.63% faster than Selection Sort sort.

type QuickSort struct{}

func (s *QuickSort) sort(data []int) {
	if len(data) < 2 {
		return
	}

	left, right := 0, len(data)-1
	pivotIndex := rand.Int() % len(data)
	data[pivotIndex], data[right] = data[right], data[pivotIndex]
	for i := range data {
		if data[i] < data[right] {
			data[i], data[left] = data[left], data[i]
			left++
		}
	}
	data[left], data[right] = data[right], data[left]
	s.sort(data[:left])
	s.sort(data[left+1:])
}

func BenchmarkQuickSort_sort(b *testing.B) {
	var s QuickSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Quick Sort sort

By Run Count

By CPU Core Count

Selection Sort

This benchmark uses the Selection Sort algorithm to sort the array. Selection Sort works by repeatedly selecting the smallest element from the unsorted part of the array and putting it at the end of the sorted part of the array.

Comparison

• Selection Sort sort is 35.50% faster than Bubble Sort sort.
• Selection Sort sort is 440.60% slower than Builtin Sort sort.
• Selection Sort sort is 116.81% slower than Insertion Sort sort.
• Selection Sort sort is 153.44% slower than Merge Sort sort.
• Selection Sort sort is 595.83% slower than Quick Sort sort.

type SelectionSort struct{}

func (s *SelectionSort) sort(data []int) {
	n := len(data)
	for i := 0; i < n; i++ {
		minIdx := i
		for j := i + 1; j < n; j++ {
			if data[j] < data[minIdx] {
				minIdx = j
			}
		}
		data[i], data[minIdx] = data[minIdx], data[i]
	}
}

func BenchmarkSelectionSort_sort(b *testing.B) {
	var s SelectionSort
	for i := 0; i < b.N; i++ {
		data := rand.Perm(1000)
		s.sort(data)
	}
}

Selection Sort sort

By Run Count

By CPU Core Count