Let us use our algorithm to see if it works:
a = [82, 10, 89, 62, 77, 62, 63, 73, 95, 73, 74, 53, 14, 18, 41]mergesort(a)
# out: [10, 14, 18, 41, 53, 62, 62, 63, 73, 73, 74, 77, 82, 89, 95]
Great! This is all you need to understand how and why this algorithm works. The only question that remains is how fast this algorithm actually is. Recursion might seem complicated, especially if you want to compute run times. We will see that this is not the case.
I won’t formally introduce run time analysis and the big O notation here — instead, we do it in a down to earth way. I will use the word step to describe something simple like
- comparing two elements
- append something to an array
- check if an array is empty
among other things. In the end, we can state something like
If the input size of the problem is n, the algorithm takes T(n) steps to output the solution.
We want to quantify this T(n).