package main

import (
   "fmt"
   "sync"
)

var waitGroup sync.WaitGroup

func main() {

   data := []int{2, 3, 5, 1, 4, 5, 2, 13, 51, 9, 10, 15, 17, 6, 21, 33, 44, 77, 22}
   fmt.Println(data)

   waitGroup.Add(1)
   go performQuickSort(data)

   waitGroup.Wait()

   var index = binarySearch(data, 4)
   fmt.Println(index)
}

func performQuickSort(data []int) {
   defer waitGroup.Done()
   quickSort(data, 0, len(data)-1)
   fmt.Println(data)
}

func quickSort(data []int, left int, right int) {
   index := partition(data, left, right)

   if left < index-1 {
      quickSort(data, left, index-1)
   }

   if right > index {
      quickSort(data, index, right)
   }
}

func partition(data []int, left int, right int) int {
   i := left
   j := right

   pivot := data[left+(right-left)/2]

   for i <= j {

      for data[i] < pivot {
         i++
      }

      for data[j] > pivot {
         j--
      }

      if i <= j {
         temp := data[i]
         data[i] = data[j]
         data[j] = temp
         i++
         j--
      }
   }

   return i;
}

func binarySearch(data []int, target int) int {

   left := 0;
   right := len(data) - 1

   for left <= right {
      mid := left + (right-left)/2
      if data[mid] < target {
         left = mid + 1
      }

      if data[mid] >= target {
         right = mid - 1
      }
   }

   return left
}