Skip to content

Restore stability for sorting #196

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

Closed
JordanMartinez opened this issue Dec 24, 2020 · 3 comments · Fixed by #197
Closed

Restore stability for sorting #196

JordanMartinez opened this issue Dec 24, 2020 · 3 comments · Fixed by #197

Comments

@JordanMartinez
Copy link
Contributor

See the following:

we should still document the stability of our sort, whether it is stable or not. I’m not sure if the new sort algorithm is stable - we should verify this, and if it is, we should document this and add tests for stability (so that we don’t accidentally lose stability later)

@pete-murphy
Copy link
Contributor

pete-murphy commented Dec 26, 2020

I made a simple stability test for sortWith that appears to be failing 7ad7cfb.
sortWith fst [Tuple "a" 1, Tuple "a" 2, Tuple "a" 3, Tuple "a" 4] returns[Tuple "a" 1, Tuple "a" 3, Tuple "a" 2, Tuple "a" 4]

@hdgarrood
Copy link
Contributor

Come to think of it, imo it's quite important for our sort to be stable, since the previous implementation was (see #158) and people might have been relying on its stability.

@hdgarrood hdgarrood changed the title Add stability tests to recently merged sorting algorithm Restore stability for sorting Dec 26, 2020
@pete-murphy
Copy link
Contributor

pete-murphy commented Dec 28, 2020

Does this effectively stabilize the merge sort? (Compare indices if values are equal by comparison.)

It passes my simple tests.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants