Carter Sande wrote:. . . . The selection sort algorithm has quadratic time complexity . . .
About 14 years ago, I ran an exercise to sort 1,000,000 “random”
ints in an array. Bubble sort took about 1hr40min to sort it. The built‑in method in Arrays#sort took about 0.4sec. If you look at the
method documentation, you will find out what sort of algorithm it uses. I also counted how often a
test for inequality was made: 499,999,500,000×, i.e.
(n − 1) × n ÷ 2
If you look at
this overloading of the method, you will find they use a different algorithm, and it tells you why.
When I made my little experiment, the number of inequality tests with selection sort, which I had been taught was faster than bubble sort, was 499,999,500,000. Selection sort ran faster than bubble sort: about 1hr39min!
By calculating the comparisons made with quicksort or merge sort (
nlog(
n)) (here about 20,000,000), you can make a rough guess how long it takes to execute each stage in the process 6,000 ÷ 500,000,000,000sec (=1.2ns) for bubble sort and 0.4 ÷ 20,000,000sec (=200ns) for Arrays#sort. So Arrays#sort won't be quicker at sorting a
small array than bubble sort