5 ms·

Impressive, but I wonder what the practical benefit will be. How often do you need to sort an array of numbers? In practice you almost always want to sort an ar

• mjburgess 3y ago
  Hash their properties
  • hurril 3y ago
    And... then? You would essentially need a homomorphic hash function for that to work. I.e.: [ a, b, c ].map(hash) produces the same order. where hash: A -> B, where p, q in A. p < q => x, y in B. x < y.
    • misja111 3y ago
      True and even then, you would only have a sorted list of the object's properties. But not a sorted list of the objects themselves.
    • mjburgess 3y ago
      `ord` is a hash function which preserves alphabetical ordering, etc. It's not that hard, in many cases, to find an `f : DataDomain -> Int` st. `f(x1) < f(x2)` where `hash(x1) < hash(x2)`
• dtech 3y ago
  sorting arrays of numbers is very often ultimately used under the hood of all the nice abstractions
• rightbyte 3y ago
  Sorting an array of pointers is sorting by numbers.
  • misja111 3y ago
    Sure, but what use is that? You will have your objects sorted by the absolute value of their pointer. I guess this means you'll have your objects sorted by the order in which they are allocated in the heap. Cool, but not very useful.
    • rightbyte 3y ago
      You can do a sorted array of pointers and later check if a specific pointer is in it with binary search, etc.
      • revelio 3y ago
        Not in Java you can't.
• inetknght 3y ago
  > How often do you need to sort an array of numbers? In practice you almost always want to sort an array of objects based on one of their properties. And? If your objects are immovable then one level of indirection (pointers or indices) solves that. If your objects are moveable, then there's many (!) times where having your container sorted will improve performance.
  • misja111 3y ago
    I don't see how you can add that level of indirection if you can only sort an array of numbers. Let's say you have a Person object with property 'age' which is an Int. I can put the Person's ages into an Int Array and sort that. Where to add this indirection to get to the sorted array of Person objects?
    • inetknght 3y ago
      1. Have an immutable container of Persons named `persons` 2. Have another container named `indices` representing the index or iterator into your Persons container In C++: 3. `std::sort(begin(indices), end(indices), [&](int lhs, int rhs)->bool{ return persons[lhs].age() < persons[rhs].age(); });` I don't know Java but I am sure there are many ways to do it in Java.
      • misja111 3y ago
        Eh yes, this works, but you are not using Arrays.intSort here. Which means that the optimizations that the article is about won't apply. intSort (or any other of the sorts in the article) works purely on an Array of Ints, moving them around and comparing them to each other. It's quite hard to come up with something that we could use in every day programming that will benefit from the new optimizations.