# 743fadcefa91cea7f366bbe915b2b1a6b1fb30e610ca75728c023d50b299e88d Elan 1.2.2 guest default_profile valid

# This code is the start-point for Worksheet 'Merge sort' where the task is to implement the 'sort' function properly, and hence get all tests passing.
function sort(li as List<of String>) returns List<of String>
  return ["x"]
end function

test sort
  # Edge case: empty
  let emptyList be empty List<of String>
  assert sort(emptyList) is emptyList
  # Edge case: one item
  let li2 be ["plum"]
  assert sort(li2) is li2
  # Happy case: odd number of members
  let li3 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  # Happy case: even number of members
  let sorted3 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear", "plum", "strawberry"]
  assert sort(li3) is sorted3
  let li4 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry"]
  let sorted4 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "plum", "strawberry"]
  assert sort(li4) is sorted4
  # Edge case: already sorted
  let li5 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear", "strawberry"]
  assert sort(li5) is li5
end test

function merge(a as List<of String>, b as List<of String>) returns List<of String>
  variable result set to empty List<of String>
  if a.length() is 0 then
    set result to b
  else if b.length() is 0 then
    set result to a
  else if a[0].isBefore(b[0]) then
    set result to [a[0]].withAppendList(merge(a[1..], b))
  else
    set result to [b[0]].withAppendList(merge(a, b[1..]))
  end if
  return result
end function

test merge
  let emptyList be empty List<of String>
  assert merge(emptyList, emptyList) is emptyList
  assert merge(["orange"], ["melon"]) is ["melon", "orange"]
  let l1 be ["apple", "lime", "pear"]
  let l2 be ["apricot", "lemon", "plum"]
  assert merge(l1, l2) is ["apple", "apricot", "lemon", "lime", "pear", "plum"]
  assert merge(l2, l1) is ["apple", "apricot", "lemon", "lime", "pear", "plum"]
  assert merge(l1, emptyList) is l1
  assert merge(emptyList, l2) is l2
  assert merge(l1, l1) is ["apple", "apple", "lime", "lime", "pear", "pear"]
end test
