Which sorting algorithm should be used if complexity is required no more than O(n) and maximum performance?

Question

Java

There is a task, to write a sorting algorithm that takes as a parameter an array of a large company (ie a large array) containing the age (in years) of ordinary people. Not very strong in sorts and algorithms, but they said that QuickSort is not the best solution.

Answer 1

If the age is integer, counting sort works well . Just for O(n).

Answer 2

First, there is a strong proof that sorting an arbitrary array cannot be done in less than O(n*log(n)) operations (log here in base 2).
Secondly, sortings have many parameters: time in the best/worst/average case, extra. memory, stability.
QuickSort has O(n log n) time at average and best, and O(n^2) at worst. It is also unstable and requires O(n) memory. Under normal circumstances, this is fine, but the worst case in her is her weak point. So either take your own, or write yourself. The simplest modification to quicksort that will make the worst time O(n log n) is to randomly select the pivot. Well, read https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
There are modifications to quicksort to reduce the worst-case time to O(n log n).
In programming languages, built-in sorts are usually either quick sort with improvements, or some kind of stable sort, some kind of merge sort.

Answer 3

no sorting o(n)
max o(n logN)

Answer 4

Age in years - range, say 120 years. 8 bits Bar graph. O(n), more precisely just N :)
Array of 120 elements, one pass, output.

Answer 5

The task specifies an important condition that the age of people will be sorted, i.e. this is a range from 1900 - 2015 at a very rough estimate. It is POSSIBLE to sort per line (O(N)) using counting sort or bitwise sort.

Answer 6

Merge sort sort will sort any amount of data that can fit on a hard drive or other disk.