Quicksort in Lua

function rest(xs)
  local ys = {}
  for i = 2, #xs do
    table.insert(ys, xs[i])
  end
  return ys
end

function concat(xs, ys)
  local zs = {}
  for _, v in ipairs(xs) do
    table.insert(zs, v)
  end
  for _, v in ipairs(ys) do
    table.insert(zs, v)
  end
  return zs
end

function qsort(xs)
  if (#xs < 2) then
    return xs
  end
  local p, xs = xs[1], rest(xs)
  local lesser, greater = {}, {}
  for _, x in ipairs(xs) do
    if x < p then
      table.insert(lesser, x)
    else
      table.insert(greater, x)
    end
  end
  return concat(qsort(lesser), concat({p}, qsort(greater)))
end

xs = {3, 1, 4, 1, 5, 9}
for _, x in ipairs(qsort(xs)) do
  io.write(x .. ' ')
end
print()
-- to check if the original xs isn't destroyed
for _, x in ipairs(xs) do
  io.write(x .. ' ')
end

This works, but the code looks more complicated than it should be.

I rewrote it with using Underscore.lua and it made the code much easier to read.

_ = require 'underscore'

function concat(xs, ys)
  return _(ys):reduce(xs, function(m, x)
    return _(m):push(x)
  end)
end

function qsort(xs)
  if (#xs < 2) then
    return xs
  end
  local p, xs = xs[1], _(xs):rest()
  return concat(
    _(qsort(_(xs):select(function(x) return x < p end))):push(p),
    qsort(_(xs):select(function(x) return x >= p end)))
end

xs = {3, 1, 4, 1, 5, 9}
_(qsort(xs)):each(function(x)
  io.write(x .. ' ')
end)
print()
_(xs):each(function(x)
  io.write(x .. ' ')
end)