Rogers Blog

def insert_into_sorted_helper(sorted, element, rest)

  if rest.size == 0 then
    sorted << element
  elsif rest[0] >= element then
    (sorted << element).concat(rest)
  else
    insert_into_sorted_helper(sorted << rest[0], element, rest[1..-1])
  end 

end

# Insert an element into a already sorted list. The resulting list stays sorted.
def insert_into_sorted(sorted, element)
  insert_into_sorted_helper([],element,sorted)
end

def recursive_sort_helper(sorted, unsorted)

  if unsorted.size == 0 then
    sorted
  else
    first = unsorted[0]
    rest = unsorted[1..-1]
    recursive_sort_helper(insert_into_sorted(sorted, first), rest)
  end
end

# Sorts a list
def recursive_sort(unsorted)
  recursive_sort_helper([],unsorted)
end