# Which are the most effective sorting algorithms for a large dataset?

A bit of background, the work that I currently and will be doing involves sorting very large amounts of data (in this case, grayscale pixels in descending order), sometimes up to 4 million.

Which are the most effective and efficient sorting algorithms that could handle multiple large datasets (such as descried in the 1st paragraph)? Is there an algorithm that could simultaneously sort through 2 or more sets of pixels?

• Very large datasets (i.e. billions of elements) are usually sorted using mergesort (e.g. GNU sort, from coreutils). This can be tuned to use as much memory as is available. For a few million elements, an in-memory sort such as the qsort implementation in glibc is usually fine. – András Salamon Jun 30 '13 at 9:02
• What do you mean by “multiple large datasets”? Sorting is normally defined as operating on one dataset. Do you mean an algorithm that performs well for different types of datasets? If so, what types? You mention sorting pixels: what are you sorting them by? – Gilles 'SO- stop being evil' Jun 30 '13 at 21:11
• @Gilles clarified. – user8872 Jun 30 '13 at 23:46
• I don't understand. How would that differ from running two instances of a sorting algorithm, one on each dataset? If you want to compare two datasets, that's a different problem, and sorting may not be the best approach. – Gilles 'SO- stop being evil' Jul 1 '13 at 23:55
• "grayscale pixels" are what exactly? Values between 0 and 255? Four million of them is definitely not a large dataset. Four billion probably isn't either. If it fits in RAM, use your language's library sort. If it doesn't fit in ram try sortbenchmark.org. If it's really values between 0 and 255, use counting sort. – adrianN Mar 29 '16 at 10:29

• The algorithm used by qsort and std::sort depends on the implementation, and it's often not quicksort. – Gilles 'SO- stop being evil' Jun 30 '13 at 21:13