CMPT 225 Lecture Notes - Dspace, Heapsort, High1
4 Sep 2013
School
Department
Course
Professor
Document Summary
} 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. Normally sorting data: read in main memory, sort. Mergesort allows us to chop up the pieces and put them back together. Want to break up file between number of different processes to deal with faster. Sorting algorithms we have looked at so far: Algorithm | (avg) time complexity | (avg) space complexity | stable. Quicksort - recursive invocations pushed onto callstack. logn recursive invocations.
