Simple insertion into an ordered List

Insert.scala

val li=List(1,2,10,20,30)                         //> li  : List[Int] = List(1, 2, 10, 20, 30)

def insert[T](li:List[T],x:T)(implicit cmp:Ordering[T])={
 val (first,last)=li.partition {cmp.lteq(_, x) }
 first:::x::last
}                                                 //> insert: [T](li: List[T], x: T)(implicit cmp: Ordering[T])List[T]

insert(li,11)                                     //> res0: List[Int] = List(1, 2, 10, 11, 20, 30)
insert(li,10)                                     //> res1: List[Int] = List(1, 2, 10, 10, 20, 30)
insert(li,9)                                      //> res2: List[Int] = List(1, 2, 9, 10, 20, 30)
insert(li,0)                                      //> res3: List[Int] = List(0, 1, 2, 10, 20, 30)
insert(li,999)                                    //> res4: List[Int] = List(1, 2, 10, 20, 30, 999)

insert(List('a','b','m','z'),'l')                 //> res5: List[Char] = List(a, b, l, m, z)

You can of course use the mutable PriorityQueue

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.PriorityQueue

e.g.

val pq=collection.mutable.PriorityQueue(1,2,10,20,30).reverse
pq+=11
pq.clone.dequeueAll // to print emit in priority order

Also can use collection.immutable.SortedSet if you don't need repeated values.

e.g.

val ss=collection.immutable.SortedSet(1,2,10,20,30)
ss+11 //> res0: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 10, 11, 20,
//| 30)
ss+9 //> res1: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 9, 10, 20, 3
//| 0)
ss+10 //> res2: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 10, 20, 30)

very nice.
I was writing an imperative version and it looked ugly.
Thanks

unfortunately, partition will not exploit the fact that it is sorted and it can binary-searched into