Radix sort not working in Lua

Question

Firstly I should mention I've not been coding very long at all, although that much is probably obvious from my code :P

I'm having two problems, firstly the sort isn't functioning correctly but does sort the numbers by their length. Any help here would be appreciated.

Secondly it's changing both the table it grabs and the table it returns (not sure why). How do I prevent it changing the table it grabs?

I'd prefer if people didn't post a fully optisimised premade code as I'm not going to learn or understand anything that way.

function radix_sort(x)

   pass, bucket, maxstring = 0, x, 2 

   while true do

      pass = pass + 1
      queue = {}

      for n=#bucket,1,-1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         if pass == 1 and key_length > maxstring then
            maxstring = key_length
         end

         if key_length == pass then
            pool = string.sub(key, 1,1) 

            if queue[pool + 1] == nil then
               queue[pool + 1] = {}
            end 

            table.insert(queue[pool + 1], key)
            table.remove(bucket, n)
         end
      end

      for k,v in pairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end            
      end

      if pass == maxstring then
         break
      end
   end

   return bucket
end

Answer 1

        pool = string.sub(key, 1,1) 

always looks at the first character; perhaps you meant string.sub(key, pass, 1)

Answer 2

There's a lot of changes I made to get this working, so hopefully you can look through and pickup on them. I tried to comment as best I could.

function radix_sort(x)

   pass, maxstring = 0, 0 

   -- to avoid overwriting x, copy into bucket like this
   -- it also gives the chance to init maxstring
   bucket={}
   for n=1,#x,1 do
      -- since we can, convert all entries to strings for string functions below
      bucket[n]=tostring(x[n])
      key_length = string.len(bucket[n])
      if key_length > maxstring then
         maxstring = key_length
      end
   end

   -- not a fan of "while true ... break" when we can set a condition here
   while pass <= maxstring do

      pass = pass + 1

      -- init both queue and all queue entries so ipairs doesn't skip anything below
      queue = {}
      for n=1,10,1 do
         queue[n] = {}
      end

      -- go through bucket entries in order for an LSD radix sort
      for n=1,#bucket,1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         -- for string.sub, start at end of string (LSD sort) with -pass
         if key_length >= pass then
            pool = tonumber(string.sub(key, pass*-1, pass*-1))
         else
            pool = 0
         end

         -- add to appropriate queue, but no need to remove from bucket, reset it below
         table.insert(queue[pool + 1], key)
      end

      -- empty out the bucket and reset, use ipairs to call queues in order
      bucket={}
      for k,v in ipairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end            
      end
   end

   return bucket
end

Here's a test run:

> input={55,2,123,1,42,9999,6,666,999,543,13}
> output=radix_sort(input)
> for k,v in pairs(output) do
>   print (k , " = " , v)
> end
1    =  1
2    =  2
3    =  6
4    =  13
5    =  42
6    =  55
7    =  123
8    =  543
9    =  666
10   =  999
11   =  9999