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?

Improve this question
$\endgroup$
8
  • 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, 2013 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 'SO- stop being evil'
    Jun 30, 2013 at 21:11
  • $\begingroup$ @Gilles clarified. $\endgroup$
    – user8872
    Jun 30, 2013 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 'SO- stop being evil'
    Jul 1, 2013 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, 2016 at 10:29

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The algorithm used by qsort and std::sort depends on the implementation, and it's often not quicksort. $\endgroup$
    – Gilles 'SO- stop being evil'
    Jun 30, 2013 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.