package application

import scala.collection.JavaConverters._

  object Sorting {
    def MakeSort(mas: java.util.ArrayList[Integer]): java.util.List[Integer] = {
      @annotation.tailrec
      def Sort(notSortedMas: List[Integer], sortedMas: List[Integer]): List[Integer] = {
        notSortedMas match {
          case Nil => sortedMas
          case x::rest =>
            val (bigger, smaller) = sortedMas.partition(_ > x)
            Sort(rest, bigger ::: x :: smaller)
        }
      }
      Sort(mas.asScala.toList, List()).asJava
    }
  }

object Quicksort {
  def MakeSort(mas: java.util.ArrayList[Integer]): java.util.List[Integer] = {
    def Sort(mas: List[Integer]): List[Integer] = {
      mas match {
        case Nil => Nil
        case x::tail =>
          val (bigger, smaller) = tail partition (_ > x)
          Sort(bigger) ++ (x :: Sort(smaller))
      }
    }
    Sort(mas.asScala.toList).asJava
  }
}