![](https://cdn.pixabay.com/photo/2016/04/06/17/49/noodles-1312384_960_720.jpg)<sub>By congerdesign on pixabay.com</sub>

---

In [part 1](https://steemit.com/programming/@suesa-random/suesa-s-adventures-in-programming-part-1-of) of this, I did some easy "if then else" stuff. That was almost a month ago. Tomorrow, I have my first programming exam (of 3 this semester), and the old problem I have presents itself: I suck at studying for exams. But I learned one thing, back when I was studying for my immunology exam: It helps to explain the things I'm supposed to know for others on Steem.

And I'll do just that, with the last thing I learned: How to sort lists by merging them.

Let's start out with an unsorted list:

`[2,4,1,3,7,5,8,9,6]`

Before we can merge this list, we need to split it into at least two lists. And to do that, we need (in this case) the procedure `foldl`.

`foldl` takes a list `xs` and a procedure, to then apply to the procedure to every single element of the list, beginning with a start value `s` and then continuing with the first element of the list on the left (that's why it's called fold**l**, it starts **left**. fold**r** does the same, but from the right side.).


In practice, that'd look like this:

`
foldl f s [1,2,3,4] = f(4, f(3, f(2, f(1, s)))
`

The way brackets work, it's the most inner bracket that's calculated first, in case you're confused why it looks like the list was reversed.

Okay, now, to splitting that damn list from before!

![split.JPG](https://files.steempeak.com/file/steempeak/suesa-random/19dptnGq-split.JPG)

Some explanations:

`fn` is an unnamed procedure, which you can declare inside a procedure. Instead of a `=`, a `=>` is used.
`nil` describes the empty list `[]`.
`::`  basically means "take the element to the left and glue it in front of the element on the right".

The `split` procedure takes the first element from the list `xs` and puts it into one of the empty lists provided. It then _switches_ the places of the "still empty" list, and the one that now contains the first element, and adds the second element to the empty list. Again, places are switched, and the cycle continues, making it look like this:

`[1,2,3,4,5] [] [] -> [2,3,4,5] [1] [] -> [2,3,4,5] [] [1] -> [3,4,5] [2] [1] -> [3,4,5] [1] [2] -> [4,5] [1,3] [2] -> [4,5] [2] [1,3] -> [5] [2,4] [1,3] -> [5] [1,3] [2,4] -> [] [1,3,5] [2,4]`

And ta-da! We got the two lists `[1,3,5]` and `[2,4]` from the single list `[1,2,3,4,5]`.

Let's continue with the _merge_ part.

![merge.JPG](https://files.steempeak.com/file/steempeak/suesa-random/rxeFzKNt-merge.JPG)

`|` lets us differentiate between cases, without adding another `if then else`.
`y::yr` splits a list in two parts: The first element, or "head" `y`, and the rest, or "tail", `yr`.

If we have an empty list and a list with at least one element, merging them will give us the list that isn't empty back. But merging two? Well, if we're merging two _sorted_ lists, we get one _sorted_ list back. Look:

`
merge ([1,2] [3,4]) = Is 1 <= 3? Yes! -> 1:: merge ([2],[3,4]) -> Is 2 <= 3? Yes! -> 1::2:: merge ([],[3,4]) -> Empty list! -> 1::2::[3,4] = [1,2,3,4]
`

And if the lists are the other way around?

`
merge ([3,4],[1,2]) = Is 3<=1? No! -> 1:: merge ([3,4], [2]) -> Is 3<=2? No! -> 1::2:: merge ([3,4], []) -> Empty list! -> 1::2::[3,4] = [1,2,3,4]
`

And with an unsorted list?

`
merge ([1,3],[4,2]) = Is 1<=4? Yes! -> 1:: merge ([3],[4,2]) -> Is 3<=4? Yes! -> 1::3:: merge ([], [4,2]) -> Empty list! -> 1::3::[4,2] -> [1,3,4,2]
`

Well... it merged. But it's not sorted. Guess we need something more than that - the actual mergesort procedure.

![mergesort.JPG](https://files.steempeak.com/file/steempeak/suesa-random/O5pWp3mF-mergesort.JPG)

`let` allows us to define variables inside a procedure.
`in` defines where those variables should be used.
`end` signals the end of the `let` expression.

`mergesort` does a super fun thing. You can see that it first splits the original list `xs` into two lists, `ys` and `zs`. And `merge`? It first applies `mergesort` _again_, which splits the two lists into another two. And again. And again. Until each list only contains a single element. And _then_ they're merged.

`
[6,4,2,5,1,3,8,7] -> [6,2,1,8] [4,5,3,7] -> [6,1] [2,8] [4,3] [5,7] -> [6] [1] [2] [8] [4] [3] [5] [7]
`

And then the merging begins. Remember:

`
merge ([1,2] [3,4]) = Is 1 <= 3? Yes! -> 1:: merge ([2],[3,4]) -> Is 2 <= 3? Yes! -> 1::2:: merge ([],[3,4]) -> Empty list! -> 1::2::[3,4] = [1,2,3,4]
`

I'll simplify by only keeping the "Yes" and "No" parts.

`
6<=1? No! -> [1,6]
2<=8? Yes! -> [2,8]
4<=3? No! -> [3,4]
5<=7? Yes! -> [5,7]
`

`
[1,6] [2,8] -> 1 <= 2? Yes! 6<=2? No! 6<=8? Yes! -> [1,2,6,8]
`
`
[3,4] [5,7] -> 3<=5? Yes! 4<=5? Yes! -> [3,4,5,7]
`

`[1,2,6,8] [3,4,5,7] -> 1<=3? Yes! 2<=3? Yes! 6<=3? No! 6<=4? No! 6<=5? No! 6<=7? Yes! 8<=7? No! -> [1,2,3,4,5,6,7,8]`

And our list is sorted.

Let's hope I remember that tomorrow.