For a mental exercise, I decided to try out my own simple sorting algorithm which processes an array of integers in any order, and as it passes thru them all, records the highest and the lowest. So imagine an array of size 10 with elements (9, 2, 4, 1, 6, 8, 5, 3, 7, 0) in that order. We want the algorithm to sort them into (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). There are many ways to implement this, but the simplest I found is to use a 2nd array (call it B). After the first pass thru A, B[0] will become 0 and B[9] will become 9. Those are the smallest and largest elements in A. I also have an array of flags telling me which numbers from A I already "plucked" so I will skip over those on any subsequent passes. For simplicity, I rescan the entire array of 10 elements even on the 2nd, 3rd, 4th... passes to find the lowest and highest remaining pairs from A. This is obviously a slow algorithm since it is O($n^2$).
So I got this working quickly because it is so simple, however, it is very slow as N (the # of elements in the array to be sorted) becomes large. For example, if N=1000 vs. N=500, the N=1000 takes 4 times as long. N=2000 takes 4 times as long as N=1000....
So what I am wondering is why not have the program first break up the array into smaller arrays, sorts those, and then just merge the results into 1 big array. The question is, what is the optimal final (smallest) size array "chunks" we should work on? Breaking it up has overhead, but an n squared algorithm can go so much faster operating on small chunks, then merging the results which takes O(N) time.
For example, suppose someone wants to sort 1 million random integers and they pass me an array of those. I cannot just use my simple algorithm on that, it would take forever and a day. But is there an optimal way to break it up into pieces, or does that depend on too many things such as the compiler/interpreter, cache memory size...? Should I just try many different subarray sizes such as 1024, 512, 256... and just pick the best for my computer, timing each one? I would suspect that if breaking the subarrays too small, the overhead of doing that and merging all the tiny little pieces (such as arrays of size 2) might not be optimal, especially on a slow computer and/or in an interpreted environment (like I am using).
Also I am interested in the time complexity as the big initial array gets chopped into pieces. For example, with N=1000, I would make 1000 passes on 1000 numbers so 1 million "examinations" (array references) which is O($n^2$), however if I "chop" only once, now I would have 2 * (500$^2$) = 1/2 million + 1 merge, 4 sub-blocks would be 4 * (250$^2$) = 1/4 million but with 3 merges.... What I am thinking is eventually there will be a point of diminishing returns, meaning that chopping any smaller is of no advantage (and may actually slow things down). Question is, is trial and error the only way to find this point?