What Is the Time Complexity of Arrays.sort() and Collections.sort()
Tags: java, tutorial, programming, webdev
Published: 2022-04-07 21:56:45

Knowing time complexities are crucial for every software engineer, especially those who want to work at the top tech companies. The time complexity of sorting algorithms is especially important since its the basis for many other algorithms. This article explores the time complexity of `Arrays.sort` and `Collections.sort`, so you won't be surprised during your interview like I was.

## Same Logic Under the Hood
`Collections.sort` works on `List`s whilst `Arrays.sort` works on arrays. Inspecting the source reveals that `Collections.sort` converts the passed `List` into an array. After the conversion, `Arrays.sort` is called on the newly allocated array.

```java
{"title": "Collections.sort"}
default void sort(Comparator << ? super E > c) {
  // Convert list into array
  Object[] a = this.toArray();
  // Call Arrays.sort on newly allocated array
  Arrays.sort(a, (Comparator) c);
  ListIterator < E > i = this.listIterator();
  for (Object e: a) {
    i.next();
    i.set((E) e);
  }
}
```

## Time Complexity
As of Java 8, `Arrays.sort` uses two sorting algorithms. One is a modification of Quicksort named dual-pivot quicksort, the other an adaptation of MergeSort named Timsort. Both have a time complexity of `O(n log n)`, where `n` is the total number of items in the array.

### 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 <a href="https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html" target="_blank" rel="noopener">natural ordering</a> 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.sort`s method signatures below.

```java
public static void sort(int[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}  

public static void sort(char[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

public static void sort(float[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
```

```java
public static void sort(T[] a, Comparator<? super T> c) {
  if (c == null) {
    sort(a);
  } else {
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a, c);
    else
      TimSort.sort(a, 0, a.length, c, null, 0, 0);
   }
}
```

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.

## Conclusion
- `Arrays.sort` works an array and `Collections.sort` works on `List`s. 

- `Collections.sort` converts the `List`s into an arrays, then calls `Arrays.sort` on it. 

- `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 the passed 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.

Consider signing up for my <a href="https://gregorygaines.substack.com/subscribe">newsletter</a> or <a href="https://www.gregorygaines.com/support/">supporting me</a> if this was helpful. Thanks for reading!

## About the author.
I’m <a href="https://gregorygaines.com">Gregory Gaines</a>, a software engineer that loves blogging, studying computer science, and reverse engineering.