Hello Ellis Dee,
I have looked at Snake Sort and like it. I agree with what you say that it is about as fast as QuickSort on random data and much faster on sorted or partially sorted data. Other people call this sort a "Natural Merge Sort" but your implementation is about as fast as they get on randomly ordered data. It is possible to make it faster for partially sorted data but the added complexity will probably slow it when sorting random data.

I wouldn’t change it but there are a couple of things that are interesting to think about:

1. The buffer of ordered section details (lngIndex) only needs to be size logN. There is an elegant way to merge the sections in a binary pattern to achieve the exact same result as you have. It is marginally slower than your approach.

2. Consider the scenario when you have a lot of data that has been previously processed and is therefore in order. Then you get some new data added to the end that is not sorted. Say you look for your ordered sections and get:
Section 0: 1,000,000 elements in order
Section 1: 2 elements in reverse order
Section 2: 5 elements in order
Section 3: 7 elements in reverse order.

The binary approach that SnakeSort uses (and my suggestion above) would merge sections 0 & 1 (cost 1,000,002), then sections 2 and 3 (cost 12) and then the two results for a total cost of (1,000,002 + 12 + 1,000,014) = 2,000,028 operations.

A smarter approach would be to merge sections 1 and 2 (cost 7), then merge this with secion 3 (cost 14) and then merge this with section 0 (cost 1,000,014). The total cost of this is (7 + 14 + 1,000,014) = 1,000,035 operations.

It is most efficient to merge the smaller sections together first.

The problem is that these two ideas make the algorithm more complicated and therefore slower on random data. Unless you can think of anything.