non chunked algorithm using no regexps for faster run

[MagicalTux]

I've modified this algorithm to be faster by not using regexps (too many Go projects tend to rely on regexp too quickly, losing a lot in performances) and also to limit allocations of heap memory as much as possible.

I've edited the README with a comparative benchmark, here is it:

Before:

goos: linux
goarch: amd64
pkg: github.com/MagicalTux/natsort
cpu: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
BenchmarkSort1-12    	    6136	    300245 ns/op
PASS

After:

goos: linux
goarch: amd64
pkg: github.com/MagicalTux/natsort
cpu: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
BenchmarkSort1-12    	  606818	      2013 ns/op
PASS

I've edited the tests to add one edge case (many zeroes prefixing a number), and all tests run OK, but I'd feel safer having more tests on this.

[vbatoufflet]

Hi @MagicalTux!

Thanks for the PR, I'll take a closer look at the changes and get back at you as soon as possible.

[GwynethLlewelyn]

Heh. It's a year later — I wonder if this eventually made into the main code?

I mean, it's a 100x improvement...

[vbatoufflet]

To be fairly honest, I completely forgot about this PR. Sorry about that!

I'll try to have another look at it this week or the next :)

[GwynethLlewelyn]

No worries! I'll be around in 2026, just to check if this made it to the official repo :) Until then, I'm happily using @MagicalTux 's fork :-)

Granted, technically speaking, @MagicalTux is not using Koelle's Alphanumeric Algorithm, but rather a brand-new invention/solution which he should publicly claim as his own :-)

[ayoisaiah]

I wonder how it compares to this: https://github.com/maruel/natural

[MagicalTux]

I wonder how it compares to this: https://github.com/maruel/natural

I've run a quick test:

goos: linux
goarch: amd64
pkg: github.com/MagicalTux/natsort
cpu: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
BenchmarkSort1-12                	  921117	      1236 ns/op	      24 B/op	       1 allocs/op
BenchmarkSortMaruelNatural-12    	  666765	      1799 ns/op	      24 B/op	       1 allocs/op
PASS
ok  	github.com/MagicalTux/natsort	2.374s

Looks like my version is slightly faster. Memory usage is similar.

Also github.com/maruel/natural uses strconv.ParseUint to parse integers which means it will not properly handle digit values over 64 bits, while my version uses string comparison and has no limitations in terms of integer size (this is also probably what helps my version to be a bit faster).

[MagicalTux]

Closing pull request as I can't change the source branch.

Feel free to merge from https://github.com/MagicalTux/natsort/tree/fix-facette-natsort if you get a chance

[GwynethLlewelyn]

Awwww so sorry to hear that... I hope that there will be a chance to fix this in the future, though.