Quicksort in Scala

NaiveQuickSort.scala

object NaiveQuickSort {
  
  // naive quicksort
    
  def sort(li:List[Int]):List[Int]={
   if (li.size<2) return li
   val pivot=li.head
   val (left,right)=li.partition(_< pivot)
      
   println(left,pivot,right.tail) // debug to help make the algo clearer.
      
   sort(left) ::: pivot :: sort(right.tail)
  }                                               //> sort: (li: List[Int])List[Int]
  
  val li=List(3,8,2,5,1,4,7,6)                    //> li  : List[Int] = List(3, 8, 2, 5, 1, 4, 7, 6)
  
  sort(li)                                        //> (List(2, 1),3,List(8, 5, 4, 7, 6))
                                                  //| (List(1),2,List())
                                                  //| (List(5, 4, 7, 6),8,List())
                                                  //| (List(4),5,List(7, 6))
                                                  //| (List(6),7,List())
                                                  //| res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)
  
  sort(List())                                    //> res1: List[Int] = List()
  
  sort(List(3))                                   //> res2: List[Int] = List(3)
  
  sort(List(99,99,99,98,10,-3,2))                 //> (List(98, 10, -3, 2),99,List(99, 99))
                                                  //| (List(10, -3, 2),98,List())
                                                  //| (List(-3, 2),10,List())
                                                  //| (List(),-3,List(2))
                                                  //| (List(),99,List(99))
                                                  //| res3: List[Int] = List(-3, 2, 10, 98, 99, 99, 99)
  
  // note O(n2) when dealing with already sorted list, because of naive pivot point
  
  sort(List(1,2,3,4,5))                          //> (List(),1,List(2, 3, 4, 5))
                                                  //| (List(),2,List(3, 4, 5))
                                                  //| (List(),3,List(4, 5))
                                                  //| (List(),4,List(5))
                                                  //| res4: List[Int] = List(1, 2, 3, 4, 5)                                                
  }

QuickSort.scala

object QuickSort {
    
  // slightly less naive quicksort, pivots on centre. Uses Vectors as generally better random access than List
    
  def sort(seq:Seq[Int]):Seq[Int]={
   if (seq.size<2) return seq
   val pivotPos=seq.size/2
   val pivot=seq.apply(pivotPos)
   val (left,right)=seq.patch(pivotPos,Nil,1).partition(_< pivot) // take out pivot before we partition
      
   println(left,pivot,right)
      
   (sort(left):+ pivot) ++ sort(right)
  }                                               //> sort: (seq: Seq[Int])Seq[Int]
  
  
  val v=Vector(3,8,2,5,1,4,7,6)                   //> v  : scala.collection.immutable.Vector[Int] = Vector(3, 8, 2, 5, 1, 4, 7, 6)
                                                  //| 
  
  sort(v)                                         //> (Vector(),1,Vector(3, 8, 2, 5, 4, 7, 6))
                                                  //| (Vector(3, 2, 4),5,Vector(8, 7, 6))
                                                  //| (Vector(),2,Vector(3, 4))
                                                  //| (Vector(3),4,Vector())
                                                  //| (Vector(6),7,Vector(8))
                                                  //| res0: Seq[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8)
  
  sort(Vector())                                  //> res1: Seq[Int] = Vector()
  
  sort(Vector(3))                                 //> res2: Seq[Int] = Vector(3)
  
  sort(Vector(99,99,99,98,10,-3,2))               //> (Vector(10, -3, 2),98,Vector(99, 99, 99))
                                                  //| (Vector(),-3,Vector(10, 2))
                                                  //| (Vector(),2,Vector(10))
                                                  //| (Vector(),99,Vector(99, 99))
                                                  //| (Vector(),99,Vector(99))
                                                  //| res3: Seq[Int] = Vector(-3, 2, 10, 98, 99, 99, 99)
   
   sort(Vector(1,2,3,4,5))                        //> (Vector(1, 2),3,Vector(4, 5))
                                                  //| (Vector(1),2,Vector())
                                                  //| (Vector(4),5,Vector())
                                                  //| res4: Seq[Int] = Vector(1, 2, 3, 4, 5)
                                                  
   sort(Vector(5,4,3,2,1))                        //> (Vector(2, 1),3,Vector(5, 4))
                                                  //| (Vector(),1,Vector(2))
                                                  //| (Vector(),4,Vector(5))
                                                  //| res5: Seq[Int] = Vector(1, 2, 3, 4, 5)
  }

RandomQuickSort.scala

object RandomQuickSort {
    
  // pivots randomly as opposed to mid point, to avoid degenerate O(n2) behaviour
  // will of course emit different debug on each run, but with same result
    
  def sort(seq:Seq[Int]):Seq[Int]={
   if (seq.size<2) return seq
   val pivotPos=scala.util.Random.nextInt(seq.size) // the only difference from prev QuickSort.scala
   val pivot=seq.apply(pivotPos)
   val (left,right)=seq.patch(pivotPos,Nil,1).partition(_< pivot) // take out pivot before we partition
      
   println(left,pivot,right)
      
   (sort(left):+ pivot) ++ sort(right)
  }                                               //> sort: (seq: Seq[Int])Seq[Int]
  
  
  val v=Vector(3,8,2,5,1,4,7,6)                   //> v  : scala.collection.immutable.Vector[Int] = Vector(3, 8, 2, 5, 1, 4, 7, 6)
                                                  //| 
  
  sort(v)                                         //> (Vector(3, 2, 1),4,Vector(8, 5, 7, 6))
                                                  //| (Vector(2, 1),3,Vector())
                                                  //| (Vector(),1,Vector(2))
                                                  //| (Vector(5, 6),7,Vector(8))
                                                  //| (Vector(),5,Vector(6))
                                                  //| res0: Seq[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8)
  
  sort(Vector())                                  //> res1: Seq[Int] = Vector()
  
  sort(Vector(3))                                 //> res2: Seq[Int] = Vector(3)
  
  sort(Vector(99,99,99,98,10,-3,2))               //> (Vector(-3),2,Vector(99, 99, 99, 98, 10))
                                                  //| (Vector(98, 10),99,Vector(99, 99))
                                                  //| (Vector(),10,Vector(98))
                                                  //| (Vector(),99,Vector(99))
                                                  //| res3: Seq[Int] = Vector(-3, 2, 10, 98, 99, 99, 99)
   
   sort(Vector(1,2,3,4,5))                        //> (Vector(1, 2, 3),4,Vector(5))
                                                  //| (Vector(1),2,Vector(3))
                                                  //| res4: Seq[Int] = Vector(1, 2, 3, 4, 5)
                                                  
   sort(Vector(5,4,3,2,1))                        //> (Vector(1),2,Vector(5, 4, 3))
                                                  //| (Vector(3),4,Vector(5))
                                                  //| res5: Seq[Int] = Vector(1, 2, 3, 4, 5)
}