func main()
    a = [];
    while (0 == 0)
        print("Input a size of array: ");
        n = int(scan());
        if (n <= 0)
            break;
        endif

        # Generate a random array of length n
        clear(a);
        i = 0;
        while (i < n)
            x = randrange(100000)/100.;
            append(a, x);
            i = i + 1;
        endwhile
        printArray(a);
        println("Sorting...");

        sort(a);

        printArray(a);
        println("----");
    endwhile
endfunc

func printArray(ref a)
    i = 0;
    while (i < len(a))
        if (i > 0)
            # Separator
            if (i%10 == 0)
                println();
            else
                print(" ");
            endif
        endif
        print(a[i]);
        i = i + 1;
    endwhile
    println();
endfunc

func sort(ref a)
    l = []; r = [];
    func partition(b, e, pivotIdx)
        nonlocal a, l, r;
        clear(l); clear(r);
        x = a[pivotIdx];
        i = b;
        while (i < e)
            if (i != pivotIdx)
                if (a[i] <= x)
                    append(l, a[i]);
                else
                    append(r, a[i]);
                endif
            endif
            i = i + 1;
        endwhile
        pivotIdx = b + len(l);
        i = b;
        while (i < e)
            if (i < pivotIdx)
                a[i] = l[i - b];
            elseif (i == pivotIdx)
                a[i] = x;
            else
                a[i] = r[i - pivotIdx - 1];
            endif
            i = i + 1;
        endwhile
        return pivotIdx;
    endfunc

    func qsort(b, e)    # Recursive function
        nonlocal a;
        if (e - b <= 1)
            return;
        endif
        pivotIdx = (b + e)/2;
        pivotIdx = partition(b, e, pivotIdx);
        qsort(b, pivotIdx);
        qsort(pivotIdx + 1, e);
    endfunc

    qsort(0, len(a));
endfunc

main();         # Starter