Classic sorting algorithms implemented in Go.

DualPivotQuickSort.go

func dualPivotQuickSort(arr []int, start, end int) {
	if start < end {
		lp, rp := partition(arr, start, end)
		dualPivotQuickSort(arr, start, lp-1)
		dualPivotQuickSort(arr, lp+1, rp-1)
		dualPivotQuickSort(arr, rp+1, end)
	}
}

// partition split the slice into three parts with two pivots:
// part1 < pivot1 <= part2 <= pivot2 < part3
// return the two index of pivot1 and pivot2
func partition(arr []int, start, end int) (int, int) {
	if arr[start] > arr[end] {
		arr[start], arr[end] = arr[end], arr[start]
	}

	i, j := start+1, end-1
	leftPivot, rightPivot := arr[start], arr[end]

	// k loop from i to j
	for k := i; k <= j; k++ {
		if arr[k] < leftPivot {
			arr[k], arr[i] = arr[i], arr[k]
			i++
		} else if arr[k] >= rightPivot {
			for arr[j] > rightPivot && k < j {
				j--
			}
			arr[k], arr[j] = arr[j], arr[k]
			j--

			if arr[k] < leftPivot {
				arr[k], arr[i] = arr[i], arr[k]
				i++
			}
		}
	}

	i--
	j++
	arr[start], arr[i] = arr[i], arr[start]
	arr[end], arr[j] = arr[j], arr[end]

	return i, j
}

sort.go

// Quick Sort
func quickSort(arr []int, start, end int) {
	if start >= end {
		return
	}

	p := partition(arr, start, end)
	quickSort(arr, start, p-1)
	quickSort(arr, p+1, end)
}

func partition(arr []int, start, end int) int {
	pivot := arr[end]
	i, j := start-1, end

	// do while loop
	for {
		for i++; arr[i] <= pivot && i < end; {
			i++
		}

		for j--; arr[j] > pivot && j > start; {
			j--
		}

		arr[i], arr[j] = arr[j], arr[i]

		if i >= j {
			break
		}
	}

	arr[i], arr[j] = arr[j], arr[i]
	arr[i], arr[end] = arr[end], arr[i]
	return i
}

// Merge Sort
func mergeSort(arr []int, start, end int) {
	if start < end {
		m := start + (end-start)/2
		mergeSort(arr, start, m)
		mergeSort(arr, m+1, end)
		merge(arr, start, m, end)
	}
}

func merge(arr []int, start, middle, end int) {
	var leftParts, rightParts []int
	leftParts = append(leftParts, arr[start:middle+1]...)
	rightParts = append(rightParts, arr[middle+1:end+1]...)

	i, j := 0, 0
	k := start

	for i < len(leftParts) && j < len(rightParts) {
		if leftParts[i] <= rightParts[j] {
			arr[k] = leftParts[i]
			i++
		} else {
			arr[k] = rightParts[j]
			j++
		}

		k++
	}

	for i < len(leftParts) {
		arr[k] = leftParts[i]
		i++
		k++
	}

	for j < len(rightParts) {
		arr[k] = rightParts[j]
		j++
		k++
	}
}

// Heap Sort
func heapSort(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

	// move current root to end to sort in asending order
	for j := n - 1; j >= 0; j-- {
		arr[0], arr[j] = arr[j], arr[0]

		// call max heapify on the reduced heap
		heapify(arr, j, 0)
	}

}

func heapify(arr []int, n, i int) {
	largest := i
	l, r := 2*i+1, 2*i+2

	if l < n && arr[l] > arr[largest] {
		largest = l
	}

	if r < n && arr[r] > arr[largest] {
		largest = r
	}

	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]

		heapify(arr, n, largest)
	}
}