Suesa's Adventures in Programming - Part 2/? - Mergesort

_{By congerdesign on pixabay.com}

---

In part 1 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 foldl, it starts left. foldr 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!

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.

| 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.

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.