Menu
Imagine a case where comparison of two elements is hugely expensive.
Which sorting algorithm would you use?
Which sorting algorithm uses the fewest comparisons in the average case?
What if you can expect a lot of the compared elements to be identical, say in 80% of the comparisons. Does it make a difference?
281
Some of the most well-known comparison sorts include: Quicksort. Heapsort. Shellsort.
The sorting algorithms that sort the data without comparing the elements are called non-comparison sorting algorithms. The examples for non-comparison sorting algorithms are counting sort, bucket sort, radix sort, and others.
Among the comparison based algorithms, merge sort was far better than both quick and bubble. On the average, merge sort utilized 32.261 seconds to sort all the arrays used in the experiment while quick and bubble utilized 41.05 and 165.11 seconds respectively.
Merge-insertion sort, a variant of insertion sort, was touted as the sorting algorithm with the fewest known comparisons for several decades, and is perhaps still the best freely-documented sorting algorithm for minimal comparisons:
Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46.
Glenn K. Manacher's algorithm “and later record-breaking sorting algorithms” (none of which, unfortunately, seem to be freely documented at this time) are reported to adapt the merge-insertion sort algorithm to offer even fewer comparisons.
200
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
