# 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. Jun 30, 2013 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? Jun 30, 2013 at 21:11
• @Gilles clarified.
– user8872
Jun 30, 2013 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. Jul 1, 2013 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. Mar 29, 2016 at 10:29

• The algorithm used by qsort and std::sort depends on the implementation, and it's often not quicksort. Jun 30, 2013 at 21:13