A lot of research and engineering effort is put into finding fast methods to sort an array of integers; e.g., Java's runtime library has highly-tuned methods to sort arrays of each primitive type (see java.util.DualPivotQuicksort).

What are real-world applications of these methods? What are algorithms that build on plain integer sorting?

Let me clarify: I am not asking of applications of sorting per se, I am well aware that there is plenty of them. But it seems to me, most actually require to sort more complex data types with additional data. Typically these objects/records are sorted with respect to some key field, which might well be an integer, but this is not quite the same as sorting only an array of plain integers. In particular, sorting keys with auxiliary data would not be possible using the Java methods in java.util.DualPivotQuicksort.

  • $\begingroup$ One reduces to plain integer sorting. ​ ​ $\endgroup$
    – user12859
    Commented Jan 8, 2017 at 12:51
  • 1
    $\begingroup$ @Paparazzi: He shows links to code that sorts an array of integers. Given that code, I can easily write code that will sort an array of objects with integer keys, but the code linked to sorts just integers. And its a reasonable question: Why would we care about the performance of code that can sort just integers, nothing else? $\endgroup$
    – gnasher729
    Commented Jan 8, 2017 at 17:12
  • $\begingroup$ @gnasher729 Not how read the question. Comments are not for discussion. $\endgroup$
    – paparazzo
    Commented Jan 8, 2017 at 17:22
  • $\begingroup$ @RickyDemer I'd count an interesting reduction as a valid application, if it solves a practical problem. Were you thinking of a specific problem that is reduced to integer sorting? $\endgroup$
    – Sebastian
    Commented Jan 9, 2017 at 14:46
  • $\begingroup$ Yes - "objects/records" "with respect to some" integer "key field" ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jan 9, 2017 at 14:55


Your Answer

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