A functional (almost) prelude on the topic of mergesort

I know of table.sort, yes. But thought it was fun nonetheless.

function apply(x, f)
  for i, v in ipairs(x) do
    f(v, i)
  end
end

function filter(x, f)
  local out = {}
  local fa = function(v, i)
    if f(v, i) then table.insert(out, v) end
  end
  apply(x, fa)
  return out
end

function merge(...)
  local args = { ... }
  local out = {}
  local fa = function(v)
    table.insert(out, v)
  end
  apply(args, function(v) apply(v, fa) end)
  return out
end

function sort(x)
  if #x < 2 then
    return x
  else
    local ix = math.floor(#x/2)
    local smallx = sort(filter(x, function(v) return v<x[ix] end)) 
    local samex =  filter(x, function(v) return v == x[ix] end)
    local bigx = sort(filter(x, function(v) return v>x[ix] end))
    return merge(smallx, samex, bigx)
  end
end


function  show(x)
  apply(x, print)
end

a = { 1,3,2,4,2,1,1,23,12,22 }
show(sort(a))

NB: of course this is *not* a functional style by far, since the apply() assumes the f() will have the side effects.