Skip to content

Instantly share code, notes, and snippets.

@JarkkoPFC
Last active October 17, 2022 03:46
Show Gist options
  • Save JarkkoPFC/dcae77af8ee29b7f7b80e2d79d9563e4 to your computer and use it in GitHub Desktop.
Save JarkkoPFC/dcae77af8ee29b7f7b80e2d79d9563e4 to your computer and use it in GitHub Desktop.
Bitonic sort for 64 elements
template<typename T>
void bitonic_sort64(T vals_[64])
{
int h=-1;
do
{
for(unsigned i=0; i<32; ++i)
{
unsigned idx0=2*i;
unsigned idx1=4*(i&h)-2*(i+h)-1;
T v0=vals_[idx0];
T v1=vals_[idx1];
if((idx0<idx1)^(v0<v1))
{
vals_[idx0]=v1;
vals_[idx1]=v0;
}
}
for(int hh=h; !(hh&1);)
{
hh>>=1;
for(unsigned i=0; i<32; ++i)
{
unsigned idx0=2*(i&hh)+(i&~hh);
unsigned idx1=idx0+1+~hh;
T v0=vals_[idx0];
T v1=vals_[idx1];
if(v0>v1)
{
vals_[idx0]=v1;
vals_[idx1]=v0;
}
}
}
h*=2;
} while(h!=-64);
@JarkkoPFC
Copy link
Author

JarkkoPFC commented Sep 19, 2022

HLSL implementation: https://godbolt.org/z/xbefr6aMd

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment