CSE 214 Lecture 32: Merge Sort
Document Summary
Recursively split the list in order to sort them. Once we have n lists with 1 element in them, the lists are merged based on the order. The number of recursive calls when performing merge sort is 2n-1. In a merge sort, the sorting and breaking down of the elements at each depth looks like a full binary tree. Therefore, the number of iterations is 2^d+1 - 1 like in full binary trees which is the total number of elements. D is substituted with logn so it becomes 2^logn+1 - 1. That is then simplified to 2*2^logn - 1 which gives you 2*n - 1. This type of sorting is sequential unlike recursive type of sorting. To implement this, let"s say we have an array a with n elements like 66 44 99 55. Then, we create 2 more arrays b and c where b is the first half of a and c is the second half of a.