Skip to content

Refactor Sequence::sort #4

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
gdejohn opened this issue Sep 26, 2018 · 0 comments
Open

Refactor Sequence::sort #4

gdejohn opened this issue Sep 26, 2018 · 0 comments

Comments

@gdejohn
Copy link
Owner

gdejohn commented Sep 26, 2018

Sequence::sort implements the basic "functional quicksort" (more precisely, deforested tree sort), which is O(n log n) on average but O(n^2) worst case. This should be refactored with an algorithm that is adaptive and O(n log n) worst case, but still purely functional, stable, and lazy so that it can start producing elements before the entire sequence has been sorted. Perhaps natural merge sort?

@gdejohn gdejohn changed the title Use better sorting algorithm Use better algorithm for Sequence.sort() Oct 10, 2018
gdejohn added a commit that referenced this issue Oct 26, 2018
@gdejohn gdejohn changed the title Use better algorithm for Sequence.sort() Use better algorithm for Sequence::sort Jan 21, 2019
@gdejohn gdejohn changed the title Use better algorithm for Sequence::sort Refactor Sequence::sort May 24, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant