Sorting Algorithm

Question

I am familiar with many sorting algorithms that have the following time complexities:

O(n²) for both ascending and descending order

O(log n) for both ascending and descending order

O(2n) or O(n) for ascending order only

I'm looking for a sorting algorithm that has a time complexity of O(n) and can sort in both ascending and descending order. Could you suggest one?

Answer 1

Where are you gping to use this O(n) sort algorithm ?

will you be using a linked list or array ?

Based on these answers I can recommend something relevant.

Answer 2

Morpheus I typically use arrays because they allow faster access and modification of elements

Answer 3

It depends. I don't think people should be learning other people algorithm because we never really use it and many time, you have to think and create your own sort except it follows std::sort

But for you, you have to write out the criteria to sort and minimize operation as possible. Also, except you are drawing pixels, I will not bother if it is O(n) or O(2n)

Answer 4

Sorting algorithms typically have a lower bound of O(nlogn) when comparisons are the primary mechanism for ordering elements, as established by the Comparison Sort Bound theorem.

However, non-comparison-based algorithms can achieve better time complexity under certain conditions.