require "io2"
local fmt = require "fmt"

-- Inserts item x in list a, and keeps it sorted assuming a is already sorted.
-- If x is already in a, inserts it to the right of the rightmost x.
local function insort_right(a, x, q)
    local lo = 1
    local hi = #a + 1
    local yn = "ynYN":split("")
    while lo < hi do
        local mid = (lo + hi) // 2
        ++q
        local prompt = string.format("%2d: Is %6s less than %6s ? y/n: ", q, x, a[mid])
        local less = string.lower(io.readOpt(prompt, yn)) == "y"
        if less then
            hi = mid
        else
            lo = mid + 1
        end
     end
     a:insert(lo, x)
     return q
end

local function order(items)
    local ordered = {}
    local q = 0
    for items as item do
        q = insort_right(ordered, item, q)
    end
    return ordered
end

local items = "violet red green indigo blue yellow orange":split(" ")
local ordered = order(items)
print("\nThe colors of the rainbow, in sorted order, are:")
fmt.lprint(ordered)