CMPSC 32 Lecture Notes - Lecture 7: Merge Sort, Quicksort
Document Summary
Break array into subarrays where size = 1. Merge subarrays to form a sorted larger array. Combine solutions back to solve the original problem. O(nlogn): best case void merge(int a[], size_t leftarraysize, size_t ri ghtarraysize) { // create the temparray temparray = new int[leftarraysize + rightarrays ize]; // merge left and right arrays into temp in soe ted order while ((leftcopied < leftarraysize) && (rightco pied < rightarraysize)) { if (a[leftcopied] < (a + leftarraysize) } else { temparray[copied++] = (a + leftarraysiz e)[rightcopied++]; // if elements is leftarray still exist while (leftcopied < leftarraysize) { temparray[copied++] = a[leftcopied++]; // if elements in rightarray still exist while (rightcopied < rightarraysize) { temparray[copied++] = (a + leftarraysize) // call mergesort on the left array mergesort(a, leftarraysize); // call mergesort on the right array mergesort(a + leftarraysize, rightarraysize); // merge left and right sorted arrays together merge(a,leftarraysize,rightarraysize); Recurse for each left / right portion of the array.
