Seven comparisons.lua

-- This code is available online at http://bit.ly/baas-compare

function sort( N ) -- Remember N is one indexed
    if N[ 1 ] > N[ 2 ] then -- One comparison
        N[ 1 ], N[ 2 ] = N[ 2 ], N[ 1 ]
    end

    if N[ 3 ] > N[ 4 ] then -- Two comparisons
        N[ 3 ], N[ 4 ] = N[ 4 ], N[ 3 ]
    end

    if N[ 1 ] > N[ 3 ] then -- Three comparisons
        N[ 1 ], N[ 2 ], N[ 3 ], N[ 4 ] = N[ 3 ], N[ 4 ], N[ 1 ], N[ 2 ]
    end

    -- So far we have A < C < D, and A < B

    local e_goes_to
    if N[ 3 ] > N [ 5 ] then -- Four comparisons
        if N[ 1 ] > N[ 5 ] then -- Five comparisons
            e_goes_to = 1
        else
            e_goes_to = 3
        end
    else
        if N[ 4 ] > N[ 5 ] then -- Five comparisons
            e_goes_to = 4
        else
            e_goes_to = 5
        end
    end

    if e_goes_to == 1 then
        if N[ 2 ] > N [ 3 ] then -- Six comparisons
            if N[ 2 ] > N[ 4 ] then -- Seven comparisons
                N[ 2 ], N[ 3 ], N[ 4 ] = N[ 3 ], N[ 4 ], N[ 2 ]
            else
                N[ 2 ], N[ 3 ] = N[ 3 ], N[ 2 ]
            end
        end
        table.insert( N, e_goes_to, N[ 5 ] )
        table.remove( N ) -- Removes extra e at end
    else
        table.insert( N, e_goes_to, N[ 5 ] )
        table.remove( N ) -- Removes extra e at end

        local b_goes_to
        if N[ 2 ] > N[ 4 ] then -- Six comparisons
            if N[ 2 ] > N[ 5 ] then -- Seven comparisons
                b_goes_to = 5
            else
                b_goes_to = 4
            end
        else
            if N[ 2 ] > N[ 3 ] then -- Seven comparisons
                b_goes_to = 3
            else
                b_goes_to = 2
            end
        end

        table.insert( N, b_goes_to+1, N[ 2 ] )
        table.remove( N, 2 )
    end

    assert( N[ 1 ] <= N[ 2 ] and N[ 2 ] <= N[ 3 ] and N[ 3 ] <= N[ 4 ] and N[ 4 ] <= N[ 5 ] )
end

-- The code below is JUST to prove correctness

local function contained( P, n )
    for i=1, #P do
        if P[ i ] == n then return true end
    end

    return false
end

local function copy( P )
    C = {}
    for i=1, #P do
        C[ i ] = P[ i ]
    end
    return C
end

local count = 0
for i=1, 5 do
    P = {}
    table.insert( P, i )
    for j=1, 5 do
        if not contained( P, j ) then
            table.insert( P, j )
            for k=1,5 do
                if not contained( P, k ) then
                    table.insert( P, k )
                    for l=1,5 do
                        if not contained( P, l ) then
                            table.insert( P, l )
                            for m=1,5 do
                                if not contained( P, m ) then
                                    table.insert( P, m )
                                    count = count + 1
                                    sort( copy( P ) )
                                    table.remove( P )
                                end
                            end
                            table.remove( P )
                        end
                    end
                    table.remove( P )
                end
            end
            table.remove( P )
        end
    end
    table.remove( P )
end
assert( count == 120 )