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