What is the name of this sorting method, how does it work and how does it compare to Arrays.sort()?

Q#1

I am searching for a method to sort an array in ascending order. I found this and it works, but I don’t understand how it works.

Q#2

As for the Big O notation, which method is better (n will be small in my case), the method below or Arrays.sort()?

---

for (int i = 0; i < array; i++) {
   for (int j = 0; j < array; j++) {
      if (arr[i] < arr[j]) {
         order = arr[j];
         arr[j] = arr[i];
         arr[i] = order;
      }
    }
}

Note: array is equal to arr.length.

Answer

#1

The method you are using is closest to what is called a Selection Sort. A nice illustration can be found here and a more entertaining one here.

A proper implementation of a selection sort would start the inner loop at j = i + 1 and swap at most one element per each iteration of the outer loop (the minimum or maximum of elements in the unsorted part of the array with the i-th element). As it stands, the array still gets sorted correctly, but you are doing a lot of redundant comparisons and swaps.

Also note that your if logic sorts the array in descending order (and not in ascending, as you claim that it does).

#2

The time complexity of a Selection Sort is O(n^2), whereas Arrays.sort() uses Dual Pivot Quicksort with an O(nlogn) time complexity. There is also an optimisation built into the JDK’s sorting algorithm that uses Insertion Sort on smaller arrays so there really is no reason for you to worry about performance.

---

Edit: Why is the sorting time faster using this method as opposed to using Arrays.sort()?

While the API docs state:

Implementation Note:

The sorting algorithm is a Dual-Pivot Quicksort…

the actual implementation is much more involved and contains all kinds of optimisations.

Of course, there can be a particular case where your sorting method is faster, but I would stick to using the JDK’s sorting algorithm. It has been thoroughly tested and refined to assure correctness and optimal performance.

Another thing to consider, as @GhostCat has pointed out, is that your benchmarking might be flawed. Check How do I write a correct micro-benchmark in Java? for more on that topic.