I'm new to Scala and was just reading Scala By Example. In chapter 2, the author has 2 different versions of Quicksort.
One is imperative style:
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length - 1)
}
One is functional style:
def sort(xs: Array[Int]): Array[Int] = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
The obvious advantage the functional style has over imperative style is conciseness. But what about performance? Since it uses recursion, do we pay for the performance penalty just like we do in other imperative languages like C? Or, Scala being a hybrid language, the "Scala way" (functional) is preferred, thus more efficient.
Note: The author did mention the functional style does use more memory.