MergeSort
Wednesday, February 24, 2010
9:38 AM
MergeSort
Each mapper sorts data locally. 
Parallel mergesort: reducer does not sort, but rather, merges presorted data (O(n) rather than O(n log n)).
Only small pieces get sorted in the mappers.  