Skip to content
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.

Sign up for GitHub

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

Jump to bottom

Stable vergesort #11

Open
Morwenn opened this issue Jun 18, 2018 · 1 comment
Open

Stable vergesort #11

Morwenn opened this issue Jun 18, 2018 · 1 comment

Comments

@Morwenn
Copy link
Owner

Morwenn commented Jun 18, 2018 •
edited

Theoretically, vergesort could be made stable by only looking for non-decreasing and strictly decreasing runs and using a stable sorting algorithm as a fallback instead of the current quicksort/pdqsort (this runs detection scheme is actually used by timsort to ensure the stability of the algorithm). Such a design decision would also somewhat solve the plateau problems described in #7, but would give suboptimal performance for a non-ascending sequence where one element in two compares equivalent to the previous one.
Morwenn added a commit to Morwenn/cpp-sort that referenced this issue Dec 21, 2020
@Morwenn
Add an explicit stable_adapter<verge_sorter> specializations
affe28b 
An likewise for stable_adapter<verge_adapter>. Instead of simply relying
on make_stable, the new specializations use a variant of vergesort that
detects strictly descending runs instead of non-ascending ones, and
wraps the fallback sorter in stable_t.

The technique of detecting non-descending and strictly descending runs
is a trick borrowed from timsort in order to preserve stability in
natural mergesort algorithms: descending runs are reversed in-place, so
equivalent elements wouldn't retain their original order when reversed
in such runs.

While verge_adapter does not handle bidirectional iterators, the
underlying code was changed so that it will be easier to do in the
future, but currently this involves some dirty tricks with a stripped
down implementation of a sized iterator. This will make the transition
to C++20 ranges and standard sized iterators and sentinels easier in the
long term. Meanwhile it is just an implementation detail.

This commit addresses external issue Morwenn/vergesort#11 and somehow
Morwenn/vergesort#7 too. cpp-sort is a better recipient for those
variations on vergesort than the standalone project, but some
cross-project documentation will be needed anyway.
@Morwenn
Copy link
Owner Author

Morwenn commented Dec 22, 2020

This standalone project is not the best vessel to host the stable version of vergesort, so I went and implemented it in cpp-sort instead, as a specialization of stable_adapter. It uses uses the trick described here two years ago to achieve stability.

This standalone project does need some README refactor and documentation improvement though, I'm keeping this issue open until it's done.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@Morwenn