2

Timsort is the default sort algo of Python and Java and it performs better than mergesort on roughly sorted lists. I could not find any implementation of this in Elisp. How can I find out whether there is such a thing in Emacs Lisp?

OP EDIT, adding more context:

There is a real situation to this demand. There is literally an I/O of about 30 sec (a question to the final user) in each comparison. And in 80% of the cases the list is already kind-of sorted, where timsort takes big advantage above mergesort. In my case EACH question saved worth too much! If you are curious about the project, look at this: https://github.com/felipelalli/org-sort-tasks

Related issue: https://github.com/felipelalli/org-sort-tasks/issues/3

Improve this question
  • Bear in mind that sort is written in C code. It may be optimistic to expect better performance out of an elisp sort function, even if the algorithm is superior in the circumstances. – phils May 21 '19 at 4:44
  • Have you considered that there might be none? – wasamasa May 21 '19 at 6:27
  • There is a real situation @Stefan! What @phils said doesn't make sense in my case because there is literally an I/O of about 30 sec (a question to the final user) in each comparison. And in 80% of the cases the list is already kind-of sorted, where timsort takes big advantage above mergesort. In my case EACH question saved worth too much! If you are curious, look this: github.com/felipelalli/org-sort-tasks – Felipe May 21 '19 at 23:16
  • Your use case can be a bit tricky, tho: because the user may return inconsistent answers (either by mistake or because A might be more urgent than B which is more urgent than C which is more urgent than A ;-) – Stefan May 23 '19 at 4:11
  • Yes! It's not perfect and I understand this downside. One wrong decision could ruin the entire list. But it's better this than nothing. And you always can review again, and again, and again. Also, the lib try to use priority, scheduled and deadline date before ask to the user. – Felipe May 23 '19 at 5:43
3

There is no implementation of timsort for Elisp, AFAIK. The implementation of sort is a "plain" mergesort. I can't see any reason why we wouldn't be happy to change sort to use timsort, so feel free to send a patch.

In your use case, since the limiting factor is the number of calls to the comparison function, you could implement it in naive Elisp, which should be pretty easy.

Note also that by implementing it yourself, you might be able to do even slightly better than timsort by tweaking it specifically to your expected usecases. For example, while sort is limited to using boolean answers comparing two elements, your user might be happy to more directly tell you which are the already sorted runs of entries.

Improve this answer

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.