Recursive Bogosort

# Bogosort is kind of inefficient
# Let's put a stop to all that.

def recursiveBogoSort(arr)

    if(arr.size > 3) then
        a,b = goAheadAndSplit(arr)
        return bogoSplice(recursiveBogoSort(a),recursiveBogoSort(b))
    else

        until(isSorted(arr))
            arr.shuffle!
        end

        return arr

    end

end

# Takes two sorted arrays
# Joins them into one sorted array

# If you pass unsorted arrays in, bad things will happen. Probably.

def bogoSplice(left,right)
    l = "L" * left.size
    r = "R" * right.size

    lr = (l+r).split("")

    puts left.join(",")
    puts right.join(",")

    puts left.size + right.size

    # Need to initialise the combined array somehow
    # lucky shot!

    spliced = (left + right).shuffle

    # prepare for poppery

    left.reverse!
    right.reverse!

    until(isSorted(spliced))

        lleft = left.clone
        rright = right.clone

        #puts "#"

        lr.shuffle!
        spliced = []

        lr.each do |something|
            if(something.eql?("L")) then
                spliced << lleft.pop
            else
                spliced << rright.pop
            end
        end

        #puts spliced.join("-")
        #print(".")

    end

    return spliced

end

# Array needs minimum size
# Good thing we aren't calling it under that

def goAheadAndSplit(arr)

    x = arr.size / 2

    return arr[0..x-1] , arr[x..-1]

end

# Useful helper function

def isSorted(arr)
    arr == arr.sort
end

# sample usage

lol = []

32.times do
    lol << Random.rand(4125)
end

puts recursiveBogoSort(lol).join(",")