Original Lua version: https://gist.github.com/biomood/1132659

mergesort.moon

-- [[ Implementation of MergeSort --]]

-- merge an array split from p-q, q-r
merge = (A, p, q, r) ->
  n1 = q - p + 1
  n2 = r - q
  left = {}
  right = {}

  for i = 1, n1
    left[i] = A[p+i-1]

  for i= 1, n2
    right[i] = A[q+i]

  left[n1+1] = math.huge
  right[n2+1] = math.huge

  i=1
  j=1

  for k = p, r
    if left[i] <= right[j]
      A[k] = left[i]
      i = i+1
    else
      A[k] = right[j]
      j = j+1

-- main mergesort algorithm
mergeSort = (A, p, r) ->
  -- return if only 1 element
  if p < r
    q = math.floor((p + r)/2)
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

-- fill A with random numbers between 1 and 100
randArray = (A) ->
  for i = 1, 100
    A[i] = math.random(100)

-- print all the elements in the array A
printArray = (A) ->
  for i = 1, #A
    io.write(A[i] .. ", ")
  io.write("\n")

A = {}

-- create the original array
randArray(A)
io.write("Original Array \n")
printArray(A)
io.write("\n")

-- sort the array
mergeSort(A, 1, #A)
io.write("Sorted Array \n")
printArray(A)