-
Notifications
You must be signed in to change notification settings - Fork 45
Incorrect minRunLength() computing minRun to be too small #33
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
Comments
Indeed, CPython seems to have I'm going to change it and run all the tests I have to check whether everything still works. If there isn't any obvious issue I will change it to 64. Thanks for the catch. |
Oh, I don't remember the why. Please fix it. |
So, I wouldn't change Btw, thanks for maintaining this repo (and many others). |
You're right once again, I applied your proposed resolution, thanks :) Thank you Goro too for the heads up! |
For some reason the loop condition in minRunLength was MIN_MERGE=32 while the original CPython implementation uses 64 there. This commit changes that condition to 2*MIN_MERGE to bring the condition back to 64 at it should probably have been. Thanks @weeyizhi for identifying and the fix.
Uh oh!
There was an error while loading. Please reload this page.
The following line seems incorrect.
Since MIN_MERGE is 32, the loop would end with n containing the 5 most significant bits instead of 6 most significant bits.
Therefore, the function would return [0, 32], which is less than what Python is doing here
The Python detailed description of Timsort in the readme here also corresponds to returning a size of [32, 64] when possible.
The text was updated successfully, but these errors were encountered: