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

Implement unstable counting sort #5

Open
pcclark4 opened this issue Feb 2, 2020 · 1 comment
Open

Implement unstable counting sort #5

pcclark4 opened this issue Feb 2, 2020 · 1 comment

Comments

@pcclark4
Copy link
Owner

pcclark4 commented Feb 2, 2020

No description provided.

@pcclark4
Copy link
Owner Author

pcclark4 commented Feb 8, 2020 •
edited
Loading

I'm not sure if this is actually possible? Wikipedia says it is...

https://en.wikipedia.org/wiki/Counting_sort

As described, counting sort is not an in-place algorithm; even disregarding the count array, it needs separate input and output arrays. It is possible to modify the algorithm so that it places the items into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in-place version of counting sort is not stable.[3]

I do have an in-place implementation for uint32_t values, I just don't know if it is possible for generic values.

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
@pcclark4