Iterative Quicksort in Julia that also works on CUDA

This series outlines what I am learning from building a machine learning algorithm (Neuroevolution) in Julia and attempting to make it run on GPUs (CUDA) using CUDAnative.

Recursive programming is among the things that you lose when programming on GPUs. Hence, if you need quicksort, you would need its iterative version.

Why do you want program on GPUs? Currently my Neuroevolution runs many times faster on GPUs than on CPUs. My CPU is a 2.7 GHz Intel Core i7 on a late-2016 MacBook Pro. But, my GPU is a GeForce GTX 1080 Ti, which I initially bought for gaming.

Here I adapted an iterative quicksort by Darel Rex Finley to Julia.

Please note that the algorithm would fail and return false if i ever reaches 1,000.

This version runs on Julia on CPUs, but to get it to run on GPUs (CUDA) using CUDAnative, you must also remove all the returns.

Please also note that this version of quicksort is not optimal on GPUs unless you are running multiple quicksorts concurrently to saturate the GPUs.

function qsort!(xs::Array{Int64,1}, n::Int64)
    i = 1
    begins = Array{Int64}(1000)
    ends = Array{Int64}(1000)
    begins[1] = 1
    ends[1] = n + 1
    while i >= 1
        left = begins[i]
        right = ends[i] - 1
        if left < right
            pivot = xs[left]
            if i == 1000
                return false
            end
            while left < right
                while xs[right] >= pivot && left < right
                    right -= 1
                end
                if left < right
                    xs[left] = xs[right]
                    left += 1
                end
                while xs[left] <= pivot && left < right
                    left += 1
                end
                if left < right
                    xs[right] = xs[left]
                    right -= 1
                end
            end
            xs[left] = pivot
            begins[i + 1] = left + 1
            ends[i + 1] = ends[i]
            ends[i] = left
            i += 1
        else
            i -= 1
        end
    end
    return true
end

xs = [11, 13, 14, 15, 12, 1233, 32, 1, -3, 442, 45, 55, 5, 9, 3, 132, 4, 111, 2, 994]
len = length(xs)
qsort!(xs, len)
println(xs)

OUTPUT: [-3, 1, 2, 3, 4, 5, 9, 11, 12, 13, 14, 15, 32, 45, 55, 111, 132, 442, 994, 1233]