Lua mergesort bug -

i'm trying learn lua writing basic mergesort, since i'm unfamiliar mergesorts, i've run problems.

the code:

arr = {} status = 0   function return_first_half (list)     size = #list     size = size / 2     t = {}     var = 1, size, 2         t[var] = list[var]     end     return t end  function return_last_half (list)     size = #list     = size / 2     t = {}     var = size, i, -1         t[var] = list[var]     end     return t end   function msort (list)     size = #list     first_half = {}     last_half  = {}     if (size <= 1)         return list     end     first_half = msort(return_first_half(list))     last_half = msort(return_last_half(list))     if (#first_half == 1)         if (#last_half == 1)             if (first_half[1] > last_half[1])                 arr[status] = first_half[1]                 status = status + 1                 arr[status] = last_half[1]                 status = status + 1             end             if (first_half[1] < last_half[1])then                 arr[status] = last_half[1]                 status = status + 1                 arr[status] = first_half[1]                 status = status + 1             end         end     end end  function main ()     list = {}     = 1, 8, 1         list[i] = io.read()     end     msort(list)     = 1, #arr, 1         print (arr[i])     end end  main() 

when give input 8 descending 1, prints nil , exits. help?

edit: fixed issues array lengths , adresses, returns stack overflow @ line:

first_half = msort(return_first_half(list)) 

the problem never out of recursion due error in calculating / copying first , second half.

but before start, let me point out should always use local variables temporary storage inside functions. it's faster , doesn't clutter global table. should use local (please, please used id) unless feel need set global variable.

now topic: in return_first_half copy every second item. why that? should use math.floor(size/2), if want allow uneven table sizes.

similarily in return_second_half. change to:

function return_last_half (list)     size = #list     = math.floor(size / 2) + 1     t = {}     local itemno = 1     var = i, size         t[itemno] = list[var]     end     return t end 

problems in version:

• you fractional numbers when table size uneven
• you're setting items in same positions in return table, 5, 6, 7, 8. means size # operator returns 8, although number of items 4. actually, whenever have gaps in array, behaviour of size operator undefined.

in general algorithm not designed, i'm not going go deeper. i've told how avoid stack overflow, can take there, if like.

but let me give quick implementation of mergesort, sorts items in place (puts them in same table):

local function merge(list, start, middle, stop)     local temp = {}     local itemno = 1     local item1, item2 = start, middle + 1      while item1 <= middle , item2 <= stop         if list[item2] < list[item1]             temp[itemno] = list[item2]             item2 = item2 + 1         else             temp[itemno] = list[item1]             item1 = item1 + 1         end         itemno = itemno + 1     end      if item1 <= middle         while item1 <= middle             temp[itemno] = list[item1]             itemno = itemno + 1             item1 = item1 + 1         end     else         while item2 <= stop             temp[itemno] = list[item2]             itemno = itemno + 1             item2 = item2 + 1         end     end      itemno = 1     = start, stop         list[i] = temp[itemno]         itemno = itemno + 1     end end  local function msort(list, start, stop)     if stop - start == 0         return list     elseif start > stop         error("oh crap")     end      local middle = math.floor((stop + start) / 2)     msort(list, start, middle)     msort(list, middle + 1, stop)     merge(list, start, middle, stop) end  local function main ()     list = {}     print("enter number of items:")     local = tonumber(io.read())     item = 1,         print("enter item number " .. item .. ":")         list[item] = tonumber(io.read())     end     msort(list, 1, i)     k, v in ipairs(list)         print (v)     end end  main() 

edit:

one thing note simple, recursive implementation you're gonna end stack overflow anyway, if list large enough.