How to Sort Lists with Tail Recursion in Scala | Rock the JVM

Written version: blog.rockthejv...
This video requires only basic experience with #Scala and I'm assuming beginner level, although more versed programmers will also get value out of the video (check the tips at the last 2 minutes).
In this video I'll show you how to sort lists in Scala, which is probably one of the first problems you'll get when starting out (it's also quite a common interview question). We'll do it in a purely functional way with immutable list in Scala. Then I'll show you how the intuitive solution fails for large data structures and I'll walk you through how to approach it differently: with tail recursion.
Follow Rock the JVM on:
LinkedIn: / rockthejvm
Twitter: / rockthejvm
Blog: rockthejvm.com...
-------------------------------------------------------------------------
Home: rockthejvm.com
-------------------------------------------------------------------------

[@Lumintorious]

Great video! Me and sorting algorithms started on the wrong foot years back cause I was introduced to imperative sorts, but I have to say, this declarative kind of sorting is bringing my faith back. Thanks! If only they made `tailrec` a keyword like they made `infix` in Scala3

[@rockthejvm]

Glad it helped!

[@samuelvishesh]

BRO! I love that you're answering my question here ❤️ I've worked out the solution on my end too!!!

[@rockthejvm]

Totally - your questions help inspire many of the videos here!

[@vishnuk1772]

very use full video...

[@RomanKotelnikov]

Great tutorial!
You could also spare `.reverse` call for accumulator if you would construct it `acc :+ head` instead of `head :: acc`

[@rockthejvm]

That would unfortunately make every append an O(N) operation instead of O(1) with a single reverse at the end.

[@RomanKotelnikov]

@@rockthejvm True, thanks for your reply!

[@freedom_aint_free]

I don't know how this video got recommend to me (I'm not a Scala programmer), but I guess it's because I do watch videos about functional programming in Lisp and in Haskell, and when I heard in the video that this operation "is not so easy" in functional languages, I can't help but to have a sight in my mind's eye on how the Haskell solution is short (I hope you don't mind):
--This function takes a list of numbers as an argument and returns a sorted list
sortList :: [Int] -> [Int]
sortList [] = [] --Base case for when the list is empty, return an empty list
sortList (x:xs) =
let smallerSorted = sortList [a | a

[@rockthejvm]

Nice solution. This goes in line with the classical argument for FP languages, "look, it's not that hard". The FP mindset "is not so easy" in general. And making everything tailrec (which the example in the comment is not) is trickier still.

[@DzielnyKompanion]

0:50 he had me on first half, not gonna lie

[@rockthejvm]

:D

[@y.8901]

Hello, nice video ! I want to know if you know a website where I can exercise myself for such problems, because I didn't find when I looked :/ I know about leetcode etc, but this not explicitly made for Scala even though you can use Scala... Thanks !

[@rockthejvm]

I have a course: rockthejvm.com/p/scala-functional-programming-interview-practice

[@erwannustv3583]

thanks a lot

[@rockthejvm]

Glad it helps!

[@JonathanRodriguez-oj2tj]

Great video, however, the last part with feature in the exercise where it is with the accumalter parameter, I do the example but with the following parameters
(4, (3,2,5), ())
(4, (2,5), (3))
(4, 5, (2,3))
3, 2 :: 4 :: 5
But I don't understand why this result is
Más información sobre este texto de origenPara obtener más información sobre la traducción, se necesita el texto de origen
Help me!!!

[@rockthejvm]

The lists are not supposed to be nested, if they are, you need to flatten them first.

[@rokkralj9786]

Tail recursive functions are less readable. It would be cool if the compiler could do such a rewrite automatically.
(Via some annotation, since such rewrite changes both behavior and performance charactersitics.)

[@rockthejvm]

You don't need to expose tailrec functions in your API if there are useless arguments - you can hide them inside the main API as an implementation detail.
Granted, stack-recursive functions are easier to write (and read) but at the cost of SOs. There's always a trade-off.

[@rokkralj9786]

@@rockthejvm Right, I am proposing a compiler that would rewrite stack-recursive function into tail-recursive function at compile time, without the programmer having to do it.

[@SwedeInCPH]

You can also just write;
val l = List(5, 3, 8, 1)
l.sorted
// Returns List(1, 3, 5, 8)
The meek shall inherit the earth 😂😂😂😂

[@rockthejvm]

I know - I can't be that arrogant to assume there's no sorting method in the standard lib - but that's not the point of the video. The video wants to show you how to think a recursive solution, and then how to adapt it to tailrec.