CS 2420 Lecture Notes - Lecture 5: Merge Sort, Call Stack, Quicksort
Document Summary
Recursion costs: recursion builds a new stack frame by calling a new function over and over again (calls itself, so same func tion). Invariant to data, will halve and combine even an already sorted array. Does not need to be passed in as a parameter like the comparator object. If there are many possibilities for ways to sort objects. Pivot: chooses a value in the middle of values. Left: puts all smaller elements from array to the left. Right: puts all larger elements from array to the right.