info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Windows (7's) OpenGL software implementation uses an unstable sorting algorithm
7 views
Skip to first unread message
Skybuck Flying
Aug 21, 2022, 9:33:07 AM8/21/22
to
> Who fancies a heapsort?
> https://github.com/abdelq/heapsort/blob/master/heapsort.asm
> MIPS; needs translating to x86 asm
>
> http://www.rosettacode.org/wiki/Sorting_algorithms/Heapsort#Forth
> again doesn't have a version in x86.
It was a little bit interesting to investigate heaps and heapsort.
However the algorithm is unstable.
I suspect the OpenGL software driver uses an unstable sorting algorithm for depth sorting.
This shows by the blinking/flickering triangles as they are roughly on the same depth.
If the camera stops moving then after a while the sort will become stable and the depth of the triangles stops flickering around.
Possibly a clear sign that an unstable sort is being used, most likely quicksort ! ;)
Bye,
Skybuck.
> https://github.com/abdelq/heapsort/blob/master/heapsort.asm
> MIPS; needs translating to x86 asm
>
> http://www.rosettacode.org/wiki/Sorting_algorithms/Heapsort#Forth
> again doesn't have a version in x86.
It was a little bit interesting to investigate heaps and heapsort.
However the algorithm is unstable.
I suspect the OpenGL software driver uses an unstable sorting algorithm for depth sorting.
This shows by the blinking/flickering triangles as they are roughly on the same depth.
If the camera stops moving then after a while the sort will become stable and the depth of the triangles stops flickering around.
Possibly a clear sign that an unstable sort is being used, most likely quicksort ! ;)
Bye,
Skybuck.
0 new messages