This is about a function perhaps no one has been waiting for … but who knows when it will come handy? (if you think it’s useful, please post!)
But if the key function is more complicated, its evaluation may become a serious factor; and since keys will be recalculated at each comparison of data within the sorting process, its time consumption is of a higher order than just linear: O(n.log(n)), to be precise. E.g. when a well-shuffled list of 10 elements is sorted, its key function is evaluated some 40 to 50 times. With 100 elements, the key function will be evaluated over a thousand times. A list of 2,000 elements needs a little over 40 thousand evaluations on average, meaning every single key will be recalculated 20 times! This inefficiency becomes noticeable, or even troublesome, with a large list to be sorted, and a key function that takes substantial time to calculate.
It's relatively easily solved: calculate the keys once before sorting the data, sort the data by key, and you may remove the keys after the sorting. But why do it yourself if you can ask a library function to do it for you?
Now here's where the newly developed PREPSORT function comes in:
It works with a list of indices that’s linked to a list of keys, and these are sorted together. Probably the script can be simplified such that the list of indices can be done without, but I haven’t yet figured out an acceptable general solution for that (taking into account that the data to be sorted may be anything, including elements of varying format).
It is used almost like the existing library function, except that the second slot is for the bare key function, whereas the third slot determines whether the keys will he sorted from Hi(gh) to Lo(w), or the other way around (in the existing library’s SORT these components are integrated into one comparison lambda function).
So here’s an example of calling PREPSORT vs. the library SORT:
I’m looking forward to comments!
The PREPSORT block is available at: