The order find processes the files is not determineddeterministic. It may be just the same order as the underlying system call gives, which probably depends on the underlying filesystem structure and can be essentially random. Some implementations might process the list somehow, but don't expect it to be sorted.
Let's try with a smaller file. cat frag* reproduces the right file, since shell globs do sort the filenames:
$ split -b512 orig.bin frag
$ cat frag* > new.bin
$ sha256sum orig.bin new.bin
8d12b42623eeefee872f123bd0dc85d535b00df4d42e865f993c40f7bfc92b1e orig.bin
8d12b42623eeefee872f123bd0dc85d535b00df4d42e865f993c40f7bfc92b1e new.bin
But find doesn't, so we get a different file:
$ find . -name 'frag*' -exec cat {} + > second.bin
$ sha256sum second.bin
821325739ca65d1cb568ecf3a16bd2e01ac4eef1419b4d714834fab07d2f135c second.bin
Just running find to print the names reveals this nicely:
$ find . -name 'frag*' |head -5
./fragzbgv
./fragzbmg
./fragvt
./fragyd
./fragzayc
That was on Linux and ext4. I think it uses some sort of hashing and trees to store the filenames, thus producing a random-looking order. On tmpfs, I got the list in reverse creation order, which isn't that random but still would mess up this case.
Explicitly sorting the list of filenames should help:
$ find . -name 'frag*' -print0 | sort -z | xargs -0 cat > third.bin
$ sha256sum third.bin
8d12b42623eeefee872f123bd0dc85d535b00df4d42e865f993c40f7bfc92b1e third.bin
The fact that it worked for you with 1k blocks, is probably an accident...
As an aside, I'm not sure why you're using dd bs=512 for the input there instead of just cat or giving split the filename directly. The thing dd does is reads and writes with a particular block size, but the pipe between dd and sort doesn't conserve block sizes, it's just a stream of bytes, and the filesystem really shouldn't care what blocksize you use to read the file, be it 512 (2^8) or 521 (a prime) bytes.
