0

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?

3 Answers 3

3

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.

2

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.

0

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

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.