Computer science: an idea about sorting

Self-tutoring about computer science: the tutor mentions a thought about using sorting algorithms.

Among comparison sorts, merge sort and quicksort are both, for average case, order nlogn, which seems about the best you can get with comparison sorts.

With actual examples I’ve run, quicksort tended to outperform merge sort. However, I’m aware that quicksort’s worst-case performance is order n^2, whereas merge sort’s is nlogn.

As I understand it, however, the worst case for quicksort is when the input is already sorted and you use the end as a pivot. One can perhaps mitigate this, however, by first using a modified bubble sort, which is of order n when the array is already sorted. Then, if the array is already sorted, you’re done after running the modified bubble sort; if not, you can apply the quicksort.

Just an idea:)

creel

Computerphile

cprogramming.com