package main

import (
    "fmt"
    "rand"
    "time"
    "os"
)

func dump(data []int) string {
    out := "[ "
    for _, item := range data {
        out += fmt.Sprintf("%02d ", item)
    }
    out += "]"
    return out
}

func sort(data []int, left int, right int) {
    if left < right {
        pivotIndex := left + (right - left) / 2 
        pivotValue := data[pivotIndex]
        data[pivotIndex], data[right] = data[right], data[pivotIndex]

        storeIndex := left
        for i := left; i < right; i += 1 {
            if data[i] < pivotValue {
                data[i], data[storeIndex] = data[storeIndex], data[i]
                storeIndex += 1
            }
        }

        data[storeIndex], data[right] = data[right], data[storeIndex]

        sort(data, left, storeIndex - 1)

        sort(data, storeIndex + 1, right)
    }
}

func quicksort(data []int, len int) {
    sort(data, 0, len - 1)
}

func validate(data []int, len int) {
    fmt.Printf("Validating... ")
    min := -1
    for _, item := range data {
        if min <= item { min = item } else {
            fmt.Printf("invalid!\n")
            fmt.Printf(dump(data))
            os.Exit(1)
        }
    }
    fmt.Printf("ok\n")
}

func main() {
    fmt.Printf("init... ")

    length := 10000000
    rand.Seed(time.Nanoseconds())

    data := make([]int, length);
    for pos, _ := range data { data[pos] = rand.Intn(length) }

    fmt.Printf("Sorting %d items... ", length)

    start := time.Nanoseconds()
    quicksort(data, length)
    elapsed := time.Nanoseconds() - start

    fmt.Printf("%f\n", float(elapsed) / 1000000000)
    validate(data, length)

    fmt.Printf("Validating already-sorted...\n")
    quicksort(data, length)
    validate(data, length)
}