Bubble sort
Bubble sort is one of the simplest and oldest algorithms. Each element is compared with the next element. If neither of the elements are in order, then the elements are swapped. Every element of the sequence is visited.
A water bubble moves to the surface. Does this have any relation with bubble sort? The simplicity of the bubble sort algorithm makes it the starting point to learn a sorting algorithm. Bubble sort is stable as two elements of equal values are never swapped with each other.
We are going to implement all the algorithm in persistent way. You might be thinking that, what is the meaning of persistant data structure? Persistent data structure always maintains its previous version after modification. We are going to use another concept, that is structural sharing. In order to understand structural sharing consider following code example:
scala> val sl = List('c','e','g')
sl: List[Char] = List(c, e, g)
scala> val asl = 'a':...
