class List<T : Comparable> {
  init(_ value: T) { self.value = value }
  init(_ value: T, _ next: List<T>?) {
    self.value = value
    self.next = next
  }

  var value: T
  var next: List<T>? = nil

  func length() -> Int {
    func inner(_ list: List<T>?, _ count: Int) -> Int {
      guard let list = list else { return count }
      return inner(list.next, count + 1)
    }

    return inner(self, 0)
  }
}

func cons<T>(_ head: List<T>, _ tail: List<T>?) -> List<T> {
  assert(head.next == nil)
  head.next = tail
  return head
}

func merge<T>(_ fst: List<T>?, _ snd: List<T>?) -> List<T>? {
  guard let fst = fst else { return snd }
  guard let snd = snd else { return fst }

  if fst.value < snd.value {
    return cons(List(fst.value), merge(fst.next, snd))
  } else {
    return cons(List(snd.value), merge(fst, snd.next))
  }
}

func drop<T>(_ list: List<T>?, _ count: Int) -> List<T>? {
  guard let list = list else { return nil }
  guard count != 0 else { return list }

  return drop(list.next, count - 1)
}

func take<T>(_ list: List<T>?, _ count: Int) -> List<T>? {
  guard let list = list, count != 0 else { return nil }

  func inner(_ oldList: List<T>?, _ count: Int, _ listAndLast: (List<T>, List<T>)) -> List<T> {
    let (list, last) = listAndLast

    guard let oldList = oldList, count != 0 else { return list }

    let next  = List(oldList.value)
    last.next = next

    return inner(oldList.next, count - 1, (list, next))
  }

  let last = List(list.value)
  return inner(list.next, count - 1, (last, last))
}

func sort<T>(_ list: List<T>?) -> List<T>? {
  guard let list = list else { return nil }
  let length = list.length()
  if length == 1 { return list }

  let fst = take(list, length / 2)
  let snd = drop(list, length / 2)

  return merge(sort(fst), sort(snd))
}