“Low-High” sort divide and conquer with merge… how small to make the subproblems for good efficiency?

Question

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?

Answer 1

My plan of attack is to simply try many different final block sizes such as 1024, 512, 256.... and just time them all. I chose a power of 2 block sizes cuz they can be halved in size easily without any fractions. For testing purposes, I would force the array sizes to be a perfect power of 2 so they divide perfectly. My goal is not a generic sorting algorithm but rather more of a divide and conquer optimization speed question.

So in array B, there would be sorted subarrays which I can then merge back into A, so the storage for this algorithm is roughly 2N.

Also regarding the merge part of this (or any sort using merge), why not just start with sorted arrays of size 1 and work your way up? For example, if we had an array of size 1024, start by merging adjacent pairs of numbers, then merge those pairs into quads...

Answer 2

If you break your array into groups of $k$ elements, sort them with your algorithm, and them merge them a-la mergesort, then your algorithm will take time: $O(\frac{n}{k} \cdot k^2 + n \log \frac{n}{k}) = O(n k + n\log \frac{n}{k})$.

This is minimized when $k$ is minimized. Therefore the best choice is $k=\Theta(1)$, resulting in a running time of $O(n \log n)$. This is essentially mergesort. Notice that any choice of $k = \omega(1)$ will lead to a slower algorithm, also in practice, once $n$ is big enough.

I also suspect that, even finding the best value of $k$ for your machine, this approach won't be much faster than a careful iterative implementation of merge-sort with one global auxiliary array $B$. Alternate between 1) using $A$ to store the sorted sub-arrays and merging into $B$, and 2) merging the sorted sub-arrays already in $B$ back into $A$. Process subarrays in the order you would visit the nodes of a binary tree in a a postorder DFS.