Quicksort Implementation in golang

quicksort.go

/**
 * ********************************** Quick Sort ***********************************************
 *             UNSORTED ARRAY [3, 7, 8, 5, 2, 1, 9, 6, 4]
 *                      pivot  ^
 *                      pivot:  3 arr:  [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
 *                                      [2, 1]    [5, 8, 7, 9, 6, 4 ]
 *                      pivot            ^         ^
 *                      pivot:  2 arr:  [ 1, 2 ]
 *                      pivot:  5 arr:  [ 4, 5, 7, 9, 6, 8 ]
 *                                      [ 4]   [7, 9, 6, 8 ]    --> Array with single element is sorted
 *                      pivot                   ^
 *                      pivot:  7 arr:  [ 6, 7, 9, 8 ]
 *                                      [ 6]   [9, 8 ]
 *                      pivot                   ^
 *                      pivot:  9 arr:  [ 8, 9 ]
 *
 *               SORTED ARRAY [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
 * *********************************************************************************************
 *
 * Worst-case Performance: O(n^2)
 * Best-cae Performance: O(n log n)
 * Average Performance: O(n log n)
 *
 * ********************************** Quick Sort ***********************************************
 */

// playground https://play.golang.org/p/SgQRJNt7eyM
package main

import (
	"fmt"
)

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

	fmt.Printf("Sorted Array - %v", quicksort(arr))
}

func quicksort(arr []int) []int {
	// return the array if array length is 1 or less than 1
	if len(arr) <= 1 {
		return arr
	}

	// make the first element as pivot
	pivot := arr[0]

	// i will move in right direction (away from pivot) from index position 1
	i := 1

	// j will move in left direction (towards pivot) from the last element of the array
	j := len(arr) - 1

	// iterate till i and j are not passed each other
	for i < j {
		// find the value which is larger than pivot
		for (arr[i] < pivot) && (i < len(arr)) {
			i++
		}

		// find the value which is lesser than pivot
		for (arr[j] > pivot) && j > 0 {
			j--
		}

		// if i is less than j
		// swap the value at i and j index
		// swap the larger value at i with lesser value at j
		if i < j {
			arr[i], arr[j] = arr[j], arr[i]
		}
	}

	// Swap the value at j with pivot
	// j index is the sorted position of the pivot
	// everything to its left is lesser and larger to its right.
	arr[j], arr[0] = arr[0], arr[j]

	fmt.Printf("pivot: %v, arr: %v\n", pivot, arr)

	// left side of the pivot will be a new subarray
	left := arr[:j]

	// if the length of the subarray is greater than 1
	// then quicksort the subarray
	if len(left) > 1 {
		left = quicksort(left)
	}

	// right side of the pivot will be a new subarray
	right := arr[j+1:]

	// if the length of the subarray is greater than 1
	// then quicksort the subarray
	if len(right) > 1 {
		right = quicksort(right)
	}

	// concat all the elements of the array
	// left pivot and right
	// return the sorted array
	left = append(left, pivot)
  
	return append(left, right...)
}

/**
 * OUTPUT
 *
 * pivot:  3, arr:  [ 2 1 3 5 8 7 9 6 4 ]
 * pivot:  2, arr:  [ 1 2 ]
 * pivot:  5, arr:  [ 4 5 7 9 6 8 ]
 * pivot:  7, arr:  [ 6 7 9 8 ]
 * pivot:  9, arr:  [ 8 9 ]
 *
 * SORTED ARRAY -  [ 1 2 3 4 5 6 7 8 9 ]
 */

Check out negative nubers, it's falling in error, or use uint to show sort working only with positive numbers

Failed for this input
6, 3, 5, 7, 4, 24, 6, 8, 5, 3, 1, 4, 67, 8, 53, 10