Created
August 24, 2023 19:44
-
-
Save lorenzotinfena/79f6b78a31e59ab0dbf97b2b9cf5b3c1 to your computer and use it in GitHub Desktop.
Efficient (but ugly) radix sort implementation for uint32
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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