sashaafm
Implement parallel Merge Sort
Me and @uranther talked in the Elixir Forum about trying to find a better implementation or algorithm than the current one for Enum.sort (it's Merge Sort). I've assigned this task for myself:
- Research algorithms that are better than Merge Sort
- Implement a Parallel Merge Sort
I don't think that there will be something better than Merge. It has a runtime of O(n log n) which is the best possible. One of its biggest downsides is its memory usage of O(n). The only other sorting algorithm that has O(n log n) for best/worst/avg is QuickSort (according to Wikipedia/Sorting_algorithm) and it has a memory usage of O(log n) (up to O(n)) while not beeing stable, and also as far as I know is not that easy to parallelize.
A good implemented Parallel Merge can "feel" like it were sorting in O(n), but does probably increase memory usage further, I didn't do any research on that right now, my son doesn't want to see me sitting at the computer :)
