package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "sort"
    "strconv"
    "time"
)

func checkErr(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

func qsort(nums []int) {
    if len(nums) <= 1 {
        return
    }
    i := 0
    j := len(nums) - 1

    m := nums[0]
    minBlank := true
    blankPos := 0
    for i <= j {
        if minBlank {
            if nums[j] < m {
                nums[blankPos] = nums[j]
                blankPos = j
                minBlank = false
            }
            j--
        } else {
            if nums[i] > m {
                nums[blankPos] = nums[i]
                blankPos = i
                minBlank = true
            }
            i++
        }
    }
    nums[blankPos] = m
    qsort(nums[:blankPos+1])
    qsort(nums[blankPos+1:])
}

func main() {

    numFile, err := os.Open("numbers.txt")  // this file have 10,000,000 rand number
    checkErr(err)
    defer numFile.Close()

    nums1 := []int{}
    nums2 := []int{}
    nums3 := []int{}
    scanner := bufio.NewScanner(numFile)
    for scanner.Scan() {
        n, err := strconv.Atoi(scanner.Text())
        checkErr(err)
        nums1 = append(nums1, n)
        nums2 = append(nums2, n)
        nums3 = append(nums3, n)
    }
    checkErr(scanner.Err())

    t1 := time.Now().UnixNano()
    qsort(nums1)
    t1 = time.Now().UnixNano() - t1

    t2 := time.Now().UnixNano()
    sort.Ints(nums2)
    t2 = time.Now().UnixNano() - t2

    t3 := time.Now().UnixNano()
    sort.Stable(sort.IntSlice(nums3))
    t3 = time.Now().UnixNano() - t3

    for k, v := range nums1 {
        // fmt.Println(v, nums2[k])
        if v != nums2[k] {
            fmt.Println("error")
        }
    }
    fmt.Println(t1)
    fmt.Println(t2)
    fmt.Println(t3)
}