How to save one counter for several recursive calls?

Question

I am trying to track the amount of comparison between array elements created in a merge sort. The program is written in Lua. I try to use multiple results and track the counter, but it does not work. Are there any other suggestions?

This is my first post, so sorry if this is dirty. Thanks!

function merge_sort (src_array) if #src_array <= 1 then return src_array else local a1, a2 = split_array(src_array) -- splitting array to sort return merge( -- merge the results recursively merge_sort(a1), merge_sort(a2)) end end 

Answer 1

I am trying to use multiple results and track the counter

If you want to do this using multiple results, you will need to modify the recursive call. Each function should return a sorted array along with the number of comparisons needed to sort it:

 local s1, n1 = merge_sort(a1) local s2, n2 = merge_sort(a2) local s, n = merge(s1, s2) return s, n1 + n2 + n 

Your basic example will look like

 return src_array, 0 

I think that maybe an additional result is not worth it, and you are better off with a local counter and a nested merge function:

 function merge_sort (src_array) local n = 0 -- number of comparisons local function merge(a1, a2) -- merge a1 and a2, incrementing n at each comparison -- return merged array end local function sort(a) if #a <= 1 then return a else local a1, a2 = split_array(a) -- splitting array to sort return merge( -- merge the results recursively sort(a1), sort(a2)) -- recursive call to `sort` *not* `merge_sort` end end local sorted = sort(src_array) return sorted, n end 

Answer 2

Use upvalue (i in the example below):

 do local i = 0 function foo () if i>= 100 then return i end i = i + 1 return foo()+foo() end end