Library Implementation of Arrays.sort() in Java with examples - David-Chae/Algorithms_Notes_Solutions GitHub Wiki

Summary

  • Arrays.sort works an array and Collections.sort works on Lists.
  • Collections.sort converts Lists into arrays then calls Arrays.sort.
  • Arrays.sort has two different sorting algorithms. Quicksort, a non-stable algorithm, and Timsort, a stable algorithm. Both share a time complexity of O(n log n), where n is the total number of items in the array.
  • Including the comparator is O(n * (log n) * c), where c is the time complexity of the comparator.
  • Arrays.sort determines which sorting algorithm to use based on the type of parameter. Quicksort for primitive data types and Timsort for objects.
  • A stable sorting algorithm means items of equal value stay in the same order after sorting.

With a Comparator

The time complexity including the comparator is O(n * (log n) * c), where c is the time complexity of the comparator. By default, Arrays.sort uses a comparator following the natural ordering of the content for an O(1) time complexity. Programmer-defined comparators with little computational work also resolve to an O(1) time complexity.

Let's say you define a comparator that had to search through files for a time complexity of O(f), where f is the number of files. The time complexity for sorting results to O(n * (log n) * (O(f) + O(f)) or O(n * (log n) * O(f)), accounting for the O(f) algorithm that runs on each comparison.

Which Algorithm is Used

The parameter type decides the chosen sorting algorithm. Take note of Arrays.sorts method signatures below. Quicksort is used on following primitive data types.

We learn that Quicksort accepts primitive data types while Timsort accepts generics. The reason being Timsort is a stable sorting algorithm while Quicksort isn't. A stable sorting algorithm means if two items of equal value sit next to each other, they will maintain the same order after sorting.

When dealing with primitive data types, two integers swapping positions doesn't matter since they are essentially equal and you can't notice a difference. On the other hand, when sorting objects, equal objects unnecessarily swapping positions can cause harmful effects. Not to mention objects can contain distinct properties which can identify when a swap is made.

Reference: