Skip to content

Instantly share code, notes, and snippets.

@lorenzotinfena

lorenzotinfena/sort.go

Created August 24, 2023 19:44
Show Gist options
  • Save lorenzotinfena/79f6b78a31e59ab0dbf97b2b9cf5b3c1 to your computer and use it in GitHub Desktop.
Save lorenzotinfena/79f6b78a31e59ab0dbf97b2b9cf5b3c1 to your computer and use it in GitHub Desktop.
Download ZIP
Efficient (but ugly) radix sort implementation for uint32
Raw
sort.go
func Sort(v []uint32) {
rec0 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<0) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
}
rec1 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<1) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec0(L, r)
}
if l < R {
rec0(l, R)
}
}
rec2 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<2) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec1(L, r)
}
if l < R {
rec1(l, R)
}
}
rec3 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<3) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec2(L, r)
}
if l < R {
rec2(l, R)
}
}
rec4 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<4) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec3(L, r)
}
if l < R {
rec3(l, R)
}
}
rec5 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<5) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec4(L, r)
}
if l < R {
rec4(l, R)
}
}
rec6 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<6) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec5(L, r)
}
if l < R {
rec5(l, R)
}
}
rec7 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<7) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec6(L, r)
}
if l < R {
rec6(l, R)
}
}
rec8 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<8) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec7(L, r)
}
if l < R {
rec7(l, R)
}
}
rec9 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<9) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec8(L, r)
}
if l < R {
rec8(l, R)
}
}
rec10 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<10) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec9(L, r)
}
if l < R {
rec9(l, R)
}
}
rec11 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<11) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec10(L, r)
}
if l < R {
rec10(l, R)
}
}
rec12 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<12) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec11(L, r)
}
if l < R {
rec11(l, R)
}
}
rec13 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<13) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec12(L, r)
}
if l < R {
rec12(l, R)
}
}
rec14 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<14) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec13(L, r)
}
if l < R {
rec13(l, R)
}
}
rec15 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<15) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec14(L, r)
}
if l < R {
rec14(l, R)
}
}
rec16 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<16) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec15(L, r)
}
if l < R {
rec15(l, R)
}
}
rec17 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<17) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec16(L, r)
}
if l < R {
rec16(l, R)
}
}
rec18 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<18) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec17(L, r)
}
if l < R {
rec17(l, R)
}
}
rec19 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<19) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec18(L, r)
}
if l < R {
rec18(l, R)
}
}
rec20 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<20) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec19(L, r)
}
if l < R {
rec19(l, R)
}
}
rec21 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<21) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec20(L, r)
}
if l < R {
rec20(l, R)
}
}
rec22 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<22) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec21(L, r)
}
if l < R {
rec21(l, R)
}
}
rec23 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<23) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec22(L, r)
}
if l < R {
rec22(l, R)
}
}
rec24 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<24) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec23(L, r)
}
if l < R {
rec23(l, R)
}
}
rec25 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<25) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec24(L, r)
}
if l < R {
rec24(l, R)
}
}
rec26 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<26) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec25(L, r)
}
if l < R {
rec25(l, R)
}
}
rec27 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<27) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec26(L, r)
}
if l < R {
rec26(l, R)
}
}
rec28 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<28) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec27(L, r)
}
if l < R {
rec27(l, R)
}
}
rec29 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<29) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec28(L, r)
}
if l < R {
rec28(l, R)
}
}
rec30 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<30) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec29(L, r)
}
if l < R {
rec29(l, R)
}
}
rec31 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<31) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec30(L, r)
}
if l < R {
rec30(l, R)
}
}
rec31(0, len(v)-1)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment