Class Notes (835,117)
CMPT 225 (60)
John Edgar (28)
Lecture

# CMPT 225 Week 7 Lecture 3

3 Pages
101 Views

School
Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
void merge(arr[], low1, high1, low2, high2) { i1 = low1; i2 = low2; itemp = 0; temp = new [high2 - low1 + 1]; // temp array to store everything while(i1 <= high1 && i2 <= high2) { // only when still processing data in BOTH subarrays if (arr[i1] < arr[i2]) { itemp = arr[i1]; i1++ } else { itemp = arr[i2]; i2++ } itemp++; } // only one of these while loops will be true while(i1 <= high1) { temp[itemp++] = arr[i1++]; } while(i2 <= high2) { temp[itemp++] = arr[i2++]; } // still need to write over contents of original array for (itemp = 0; itemp < (high2 - low1 + 1); itemp++) { arr[low1 +itemp] = temp[itemp]; } delete[] temp; } Nothing in here varies based on order of data; always same amount of work. This makes it very useful for external sorting and parallel processing. External sorting: common in databases. Normally sorting data: read in main memory, sort. What happens when file doesn't fit in main memory because it is too big? External sorting - external storage. Mergesort allows us to chop up the pieces and put them back together. Same for parallel processing. Want to break up file between number of different processes to deal with faster. SortingAlgorithms we have looked at so far: Algorithm | (Avg) Time Complexity | (Avg) Space Complexity | Stable Selection | O(n^2) | O(1) | No Insertion | O(n^2) | O(1) | Yes Quicksort | O(nlogn) | O(logn) | No Mergesort | O(nlogn) | O(n) | Yes Heapsort | O(nlogn) | O(1) | No Quicksort - recursive invocations pushed onto callstack. logn recursive invocations. Heapsort - as long as they implement bubble up and down iteratively, do everything in place. What is stable? How common is it, really, to sort giant files of integers? Much more likely to be sorting complex data types. Data with more than one attribute. Student records, etc. Can be sorted by multiple values. Examp
More Less

Related notes for CMPT 225
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.