Which algorithm is used for sorting files on hard disk?
Printable View
Which algorithm is used for sorting files on hard disk?
If the file fits in memory you can read it into an array, sort it using the algorithm that comes with your language's standard library, and then write it back again.
The Java documentation offers this note,
"The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations."
In C++ you have a choise of three algorithms: sort, partial_sort and stable_sort. They're based on quicksort, heapsort and mergesort respectively most likely with modifications not to freak out on strange data sets.
If the file is too big for memory it's another ballgame,
http://en.wikipedia.org/wiki/External_sorting