smoothsort.lua

--an implementation of smoothsort.
--the code is in a "monadic" style for fun. 
--you should [probably] not actually code like this.

function leonardo(n)
   local function lc(i, j, n)
      return n > 1 and lc(j, i+j+1, n-1) or j
   end
   return lc(1, 1, n)
end

function swap(arr, i, j)
   return function()
      arr[i], arr[j] = arr[j], arr[i]
   end
end

function leonardoheap(arr, fin, dep, new)
   new = new or arr[fin]

   if dep < 2 then
      return {}
   end

   local prev = fin - leonardo(dep-2) - 1
   local pdep = dep-1

   if arr[fin - 1] >= arr[prev] then
      prev = fin - 1
      pdep = dep - 2
   end

   if new >= arr[prev] then 
      return {} 
   end

   local swaps = leonardoheap(arr, prev, pdep, new)
   if swaps then
      swaps[#swaps+1] = swap(arr, fin, prev)
   end

   print(#swaps)
   return swaps
end

function fdep(tree)
   if tree < 1 then return error"invalid fdep" end

   for i = 1, tree do

      if leonardo(i) > tree then
         return i-1, fdep(tree - leonardo(i-1))

      elseif leonardo(i) == tree then
         return i
      end

   end
end

function leonardostack(arr, ind, tree, dept)

   if ind < 1 then return {} end

   local tree = tree or ind
   local dept = dept or {fdep(tree)}
   local dmax = table.remove(dept) --pop!
   
   local prevtree = tree - leonardo(dmax)

   local nexttree = false

   if #dept > 0 then

      nexttree = arr[prevtree] > arr[ind]

      if leonardo(dmax) ~= 1 then
         nexttree = nexttree and 
                    arr[prevtree] > arr[tree-1] and 
                    arr[prevtree] > arr[tree-leonardo(dmax-2)]
      end
   end

   if not nexttree then
      return leonardoheap(arr, tree, dmax, arr[ind])
   end

   swaps = leonardostack(arr, ind, prevtree, dept)
   swaps[#swaps+1] = swap(arr, tree, prevtree)
   return swaps
end

function smoothsort(arr)
   local swaps

   for i = 1, #arr do
      swaps = leonardostack(arr, i)
      
      for f in function () return table.remove(swaps) end do
          f()
      end

   end

   for i = #arr, 2, -1 do
      local dept = {fdep(i-1)}
      swaps = leonardostack(arr, i - 1 - leonardo(dept[#dept])) --fuck elegance

      for f in function () return table.remove(swaps) end do
         f()
      end
    
      swaps = leonardostack(arr, i - 1)

      for f in function () return table.remove(swaps) end do
         f()
      end
   end
   return arr
end