CSE 214 Lecture 32: Merge Sort

50 views2 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers