a better merge-sort alGOrithm?

<p>I&#39;m a new gopher. Following my first book on Go - writing the sample code doing all the exercises - I decided to jump in to a study of data-structures and algorithms. </p> <p>I started easy. Bubble sort first then progressed to insertion sort, followed by merge sort. I decided to tinker with the different algorithms - insertion and merge - mostly. I coded an app that produces a random number of elements in a slice with a random number (int) in each element. Compare the sort times and display on screen. I noticed that insertion sort really shined on any array less than 1000 elements, sorting quicker than merge sort. However merge sort quickly out paced insertion sort after the array grew to element sizes greater than 2500. I experimented most of the day trying different size numbers and element sizes to 1 million with numbers ranging from zero to 10,000. </p> <p>So after a while an idea formed. Since insertion sort works so well for arrays of 1000 elements or less and merge sort is a divide and conquer algorithm what if I have insertion sort take over after merge sort has divided the array down to 1000 elements. I coded this to allow an argument - threshold - in the merge sort function so I could make both calls no-threshold / threshold and compare the sort times of the algorithms. The threshold code appears to be 3 times faster on average for any size array up to 1 million elements (integers). </p> <p>OK, I know I haven&#39;t invented a better mouse trap. I know it probably seems a bit trivial to the more experienced coders. But, am I missing something? Is this sound logic or is OZ behind the curtains having a laugh at my expense. What Algorithm can I use to test my sorted arrays. I visually inspected the small arrays but 100&#39;s of thousands? Is it possible the threshold hasn&#39;t actually sorted the array completely but just large chunks and therein lies the reason for the speed efficiency? </p> <p>Here&#39;s the code ;</p> <p><a href="https://gist.github.com/dyanceyjr/2736c1718329f0d6e182ee776d225e31" rel="nofollow">https://gist.github.com/dyanceyjr/2736c1718329f0d6e182ee776d225e31</a></p> <hr/>**评论：**<br/><br/>joncalhoun: <pre><p>Congrats on figuring this out yourself :)</p> <p>This is actually a fairly well known thing (for lack of a better word) and iirc even the standard library&#39;s sort package does something like this. See <a href="https://golang.org/src/sort/sort.go" rel="nofollow">https://golang.org/src/sort/sort.go</a></p> <p>In the standard library I believe it uses a version of quick sort and heapsort but I only glanced at the code. </p> <p>Basically, some algorithms are better with smaller datasets and some are better at chunking together large datasets into their corresponding sections, so if we merge them we can write algorithms that are faster in practice. </p> <p>Sorting algorithms are interesting because there isn&#39;t always one optimal solution. A bubble sort is better than most sorting algorithms with mostly sorted data. Some sorts do better with large datasets. Others perform better on smaller datasets. I always found them fascinating even if you rarely need to actually implement one in your day to day work.</p></pre>ops-man: <pre><p>thanks. actually I&#39;m following your blog series - Let&#39;s learn Algorithms - <a href="https://www.calhoun.io" rel="nofollow">https://www.calhoun.io</a> which in turn led to this. I&#39;ll digress for a moment to say Thanks again for your series, so far I&#39;ve learned so much directly and indirectly just following along and asking questions.</p></pre>UniverseCity: <pre><p>Python&#39;s <a href="https://en.wikipedia.org/wiki/Timsort" rel="nofollow">standard sorting algorithm</a> works exactly as you described (with some other fancy stuff thrown in). </p></pre>ops-man: <pre><p>So once I learn more of the algorithms heap, quick, radix etc... then you just code procedure for selecting the most efficient combination of algorithm to use with the selected data structure??</p></pre>UniverseCity: <pre><p>The most efficient procedure can often be mathematically derived and then implemented as a proof. </p></pre>ops-man: <pre><p>indeed. I don&#39;t have those skills. yet. honestly the math eludes me. I&#39;m trying to remedy that problem. </p> <p>Your link is a very interesting read. I&#39;ll bookmark and read a couple times more. thanks. </p></pre>joncalhoun: <pre><p>I feel like this math eludes like 50% (if not more) of people who even go to college and get a computer science degree. Sure, all of those people have to learn how to create proofs and do this, but a vast majority of them only learn enough to get by and quickly forget it after college. </p> <p>I&#39;m saying this not to say that you shouldn&#39;t give it a go, but to let you know that it isn&#39;t easy for everyone and that you shouldn&#39;t get disappointed if it is challenging.</p></pre>ops-man: <pre><p>thanks. I&#39;m trying to keep focused on data structures and algorithms. But, I get distracted. I learn new things, sometimes something that was known to me and that l lacked understanding of has light on it with this new knowledge and I&#39;m drawn to it like a moth.</p></pre>drvd: <pre><p>Just supplementing what <a href="/u/joncalhoun" rel="nofollow">u/joncalhoun</a> already explained very well.</p> <p>Take a look at the test in package sort. It uses a wide range of different types of input data: From random, to presorted, jigsaw patterns, data with lots of repetitions, unique values and even &#34;malicious&#34; input (crafted to trigger quicksorts worst case behaviour). Also look at the benchmarks.</p> <p>The threshold in sort.go to switch from quicksort to shellshort is much lower than your 1000, actually 2 orders of magnitude. Maybe you could try your algorithm with the (very clever) benchmarks of package sort?</p></pre>