quicksort.groovy

import groovy.transform.CompileStatic

@CompileStatic
void swap(int[] a, int i, int j) {
    int temp = a[i]
    a[i] = a[j]
    a[j] = temp
}

@CompileStatic
void sort1(int[] a, int l, int r) {
    int m = a[(l + r)>>1]
    int i = l
    int j = r
    while (i <= j) {
        while (a[i] < m) i++
        while (a[j] > m) j--
        if (i <= j) {
            swap(a, i, j)
            i++
            j--
        }
    }
    if (l < j) sort1(a, l, j)
    if (r > i) sort1(a, i, r)
}

@CompileStatic
void quicksort(int[] a) {
    sort1(a, 0, a.length - 1)
}

@CompileStatic
long calcBest(int[] a) {
    long best = Long.MAX_VALUE
    for (i in 0..10) {
        long t1 = System.currentTimeMillis()
        quicksort(a)
        long t2 = System.currentTimeMillis()
        best = Math.min(t2 - t1, best)
    }
    best
}

a = new int[2000000*1]
a.eachWithIndex { x, i ->
    a[i] = i * 3 / 2 + 1
    if (i % 3 == 0) a[i] = -a[i]
}

println calcBest(a)