World's most popular travel blog for travel bloggers.

swapping between sorting algorithms for small input size left over

, , No Comments
Problem Detail: 

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

Asked By : Abhimanyu Aryan
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback