0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – András Salamon Jun 30 '13 at 9:02
  • $\begingroup$ 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? $\endgroup$ – Gilles Jun 30 '13 at 21:11
  • $\begingroup$ @Gilles clarified. $\endgroup$ – user8872 Jun 30 '13 at 23:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Gilles Jul 1 '13 at 23:55
  • 1
    $\begingroup$ "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. $\endgroup$ – adrianN Mar 29 '16 at 10:29
1
$\begingroup$
  1. quick sort. in C++, it's better to use std::sort rather than qsort(), since it allows compiler to perform much better optimization (both implements quick sort algorithm)

  2. depending on your data, sometimes better: http://en.wikipedia.org/wiki/Counting_sort and http://en.wikipedia.org/wiki/Radix_sort

simultaneously perform sorts on multiple large datasets?

i've not heard of such algorithms at all. but you can distribute tasks among CPU cores. moreover, you can split one dataset between two cores, and then merge results of sorting

$\endgroup$
  • 3
    $\begingroup$ The algorithm used by qsort and std::sort depends on the implementation, and it's often not quicksort. $\endgroup$ – Gilles Jun 30 '13 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy