Algorithmic Toolbox week4 Divide and Conquer --- Sorting Problem

Selection Problem

Selection Sort

image.png

image.png

image.png

image.png

Merge Sort

merge sort

image.png

image.png

image.png

For example, it is perfectly okay to sort the sequence of size 1 million, for example, 10 to the 6th, on your laptop using merge sort algorithm.

While for the quadratic time selection sort algorithm, sorting a sequence of size 10 to the 6th, 1 million, will take roughly 10 to the 12th operations, which is too much for modern computers.

image.png

Okay, so to prove this lemma, to prove the upper bound on the running time of the merge sort algorithm, first know that to merge two parts of size n over 2 of our initial array, takes the linear time.

Namely, big O of n, because while the left part has size n over 2, the right part has size n over 2. And for merging, we basically just combo these parts from left to right.

image.png

So now what we are going to do is to account for only the work done before the recursive calls and after the recursive calls at each separate level.And we know already that it takes linear time to do this. I mean, if we have an array of size n, it takes linear time to split it into two halves. And then it takes linear time to combine the result.

So in the next video, we will show that actually no algorithm, no comparison based algorithms, to be completely formal, can sort a given sequence of n elements asymptotically faster than in n log n time. Which actually means that the merge sort algorithm is asymptotically optimal.