bubbleSort.scala

def bubbleSort[A: Ordering](xs: List[A]): List[A] = {
  @annotation.tailrec
  def bubble(ys: List[A], init: List[A], max: A): (List[A], A) = ys match {
    case Nil => (init, max)
    case h :: tail =>
      if(implicitly[Ordering[A]].compare(h, max) > 0)
        bubble(tail, max::init, h)
      else
        bubble(tail, h::init, max)
  }

  def onePass(head: A, tail: List[A]): (List[A], A) = bubble(tail, Nil, head)

  @annotation.tailrec
  def sort(zs:List[A], sorted: List[A]): List[A] = zs match {
    case Nil => sorted
    case h::t => onePass(h, t) match {
      case (init, max) => sort(init, max :: sorted)
    }
  }

  sort(xs, Nil)
}

assert(bubbleSort(1::2::3::4::Nil) == 1::2::3::4::Nil)
assert(bubbleSort(4::2::3::1::Nil) == 1::2::3::4::Nil)
assert(bubbleSort(1::4::3::2::Nil) == 1::2::3::4::Nil)
assert(bubbleSort(1::3::4::2::Nil) == 1::2::3::4::Nil)
assert(bubbleSort(1::3::2::4::Nil) == 1::2::3::4::Nil)
assert(bubbleSort(2::3::2::4::Nil) == 2::2::3::4::Nil)