3
$\begingroup$

Is it suggested to swap between sorting algorithms? Merge sort certainly performs better on large input size however Insertion sort performs better on small input size

Analysis based on there graph comparison of running time of Insertion sort and merge sort

How often people swap the algorithms they are using? For example sorting problem of size 100K with merge sort and then switching to insertion sort when problem size reached to 500 input size?

Is is advisable to follow such techniques? For small input size the constants(c) does matter and insertion sort having small constant size than merge sort will certainly perform better. I guess

$\endgroup$

2 Answers 2

4
$\begingroup$

People don't usually program their own sorting routines, and I would advise against it, unless you're implementing a non-comparison-based sort such as counting sort. Library sorting routines are optimized beyond what the casual programmer can achieve.

If you're interested in the best practices of the field, you'll have to look at library sorting routines. For example, python uses Timsort, which switches to insertion sort for small arrays. The GNU implementation of Quicksort also switches to insertion sort for small arrays. So it seems switching to insertion sort for small arrays is indeed advisable.

$\endgroup$
-1
$\begingroup$

Insertion sort is quadratic. You would never, ever consider doing insertion sort for 500 input items. Not even 50.

You can only ever discuss this matter with an actual implementation on an actual machine. So Big-O is totally irrelevant. You don't get to the stage where it is relevant. The average time to sort n items using insertion sort on a particular machine with a particular implementation with particular data, and a given cost of moving data, and a given cost of comparing data, is an interesting function. It can have big jumps, for example 4 items might take a lot less time than five and six takes the same time again. So what you do is this: For k = 1, 2, 3 etc. you implement your "switching sort": If you have more than k items then you split the data into say 3 streams that you first sort then merge, and if you have k or fewer items than you sort them with insertion sort. And then you measure how long it takes to sort 100,000 items are whatever is an interesting number, with different values of k. And you measure this, check how the time needed changes with k, and pick the best k. Be careful: If you sort 100,000 items, with merge sort splitting the data into 3, you will only ever decide for n = 33,333, n = 11,111, n = 3,703, n = 1,234, n = 411, n = 137, n = 45, n = 15, n = 5, n = 1 or 2. So be careful.

And check with different data. Don't compare integers, but real world data. For example, if you compare names, then comparing "Smith, James" and "Abraham, John" makes the decision fast, after one character. Comparing "Smith-Johnson, Abraham" and "Smith-Johnson, Abigail" takes much longer. Now compare merge sort and quick sort. Will they pass different data to your insertion sort? Absolutely. Merge sort passes consecutive data from the unsorted array. Quicksort passes data that is almost in the correct place. So "insertion sort for merge sort" can afford to do some unnecessary comparisons that "insertion sort for quick sort" can't afford.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.