When there is an array in which data is stored in descending order from the beginning, such as 5, 4, 3, 2, 1 which sorting algorithm (quick sort, merge sort...) is the best way to sort this array in ascending order? And why?

CodePudding user response：

Variations of natural merge sort or TimSort (similar to natural merge sort), will scan for increasing or decreasing sequences, reversing decreasing sequences as they are encountered. If the entire array is a decreasing sequence, then the initial scan will sort the entire array when it reverses the array.

CodePudding user response：

Among the classical sorting algorithms, heap sort will do well when the input turns out to be (almost) sorted in descending order, as then the max-heap construction phase will involve (almost) no swaps (while the most swaps would occur when the input was already sorted in ascending order).

Note that speed of sorting depends on many factors (like data type, comparison function, availability of parallel computing, memory organisation,...etc). See also comparison of heap sort with other sorts.

CodePudding user response：

The best way is to avoid sorting and just reverse the sequence.
It is very simple and fast linear algorithm.

CodePudding user response：

The best algorithm will be to just reverse the sequence instead of using any sorting methods like quicksort, merge sort, etc. Because that will be of time complexity O(N log N) whereas reversing the sequence will be linear O(N).