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

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 will become 0 and B 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?

• Are you familiar with merge sort? – Yuval Filmus Apr 25 '20 at 15:38
• @Yuval Filmus - Yes, this is a variation of mergesort but this exercise is more about finding the optimal "chop" size rather than finding a good sort algorithm. Also, this algorithm is very simple so it is easy for students to understand. My goal was to keep it simple and then use the optimal chopsize to speed it up, rather than using a better initial algorithm (such as heapsort). – David James Apr 25 '20 at 15:51

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...

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.

• If just merging subarrays of size 1 is a good algorithm, then why do we have so many other sorting algorithms such as heapsort, quicksort...? Why not always use mergesort? if even simple sorting algorithms are fairly quick on small arrays (such as 1024 elements or less), why not use them and make the merge process simpler? Divide and conquer seems to work well if you divide the work "fairly", not give almost 100% of it to the merge process. – David James Apr 26 '20 at 2:41
• You seem to imply that mergesort does not divide the work fairly, while in fact it divides it "exactly" in half. Also you seem to imply that there is some extra work to do in addition to the merge step, while the merge step is all there is! Regarding the other algorithms, Mergesort has a worst-case time complexity of $O(n \log n)$ but suffers from the additional time and space overhead of using an auxiliary array. Quicksort does not but it has a worst-case complexity of $O(n^2)$. Implementing quicksort to run in time $O(n \log n)$ is possible but more involved. – Steven Apr 26 '20 at 2:55