H Lecture 6: w4
12 Sep 2021
Department
Course
Professor
Document Summary
The top-down merge sort approach is the methodology which uses recursion mechanism. Example: let us consider an example to understand the approach better. Divide the unsorted list into n sublists, each comprising 1 element (a list of 1 element is supposed sorted). Repeatedly merge sublists to produce newly sorted sublists until there is only 1 sublist remaining. The first element of both lists is compared. If sorting in ascending order, the smaller element among two becomes a new element of the sorted list. This procedure is repeated until both the smaller sublists are empty and the newly combined sublist covers all the elements of both the sublists. #include using namespace std; void merge(int arr[], int start, int mid, int end) { // create a temp array int temp[end - start + 1]; // crawlers for both intervals and for temp int i = start, j = mid+1, k = 0;
