Why is processing a sorted array faster than processing an unsorted array in Java?

Valerie M.

The Problem

Why is processing a sorted array faster than processing an unsorted array in Java?

The Solution

Typically, when processing arrays (or broadly, data structures), four key actions are performed. These include:

• Accessing,
• Searching,
• Inserting and
• Deleting.

Accessing an element by its index or inserting or deleting elements have the same time complexity, regardless of whether an array is sorted or unsorted.

Processing a sorted array is only faster than processing an unsorted array if you’re searching for an element in the array.

Let’s take a look at how searching affects performance on sorted and unsorted arrays.

Searching a sorted array

Searching a sorted array allows you to make assumptions about where in the array the search item is meant to be. This means that you can apply algorithms that divide the array based on where that item is in the array. For example, if you’re looking for a word in a dictionary, which is usually sorted in alphabetic order.

Consider the following code example:

import java.util.Arrays;
import java.util.Objects;


public class MyClass {
    public static void main(String[] args) {
        String[] arr = {"Adrian", "Bella", "Charlotte", "Daniel", "Emma", "Hanna", "Isabella", "Jayden", "Kaylee", "Luke", "Mia", "Nora", "Olivia", "Paisley", "Riley", "Thomas", "Wyatt", "Xander", "Zoe"};

        String elem = "Luke"; // 9
        int offset = 0;
        int bS = binarySearch(arr, elem, offset);
        System.out.println("Index of search item = " + bS);
    }

    public static int binarySearch(String[] array, String element, int offset) {
        // split array in half
        int half = array.length / 2;
        String current = array[half];

        if (Objects.equals(current, element)) {
            return offset + half;
        } else if (element.compareTo(current) > 0) {
            String[] right = Arrays.copyOfRange(array, half, array.length);
            return binarySearch(right, element, offset + half);
        } else {
            String[] left = Arrays.copyOfRange(array, 0, half);
            return binarySearch(left, element, offset);
        }
    }
}

The binarySearch function is a binary search algorithm that uses a recursive method to return the index of an element in a sorted array.

The time complexity of a binary search is known to be O(log(n)). You can check out this article to see how the time complexity equation is determined for recursion.

If you were to plot the logarithmic graph for this search function, it would depict how the running time reduces at a fast rate given increasing sizes of the array which is incredible especially for very large input sizes.

Searching an unsorted array

Searching an unsorted array means that the algorithm would have to visit every element in the array in order to find the element we’re searching for. The best-case scenario would be if the search item is the first element in the array, which would have a time complexity of O(1) however, this is not always the case.

If the search item is towards the end of the array, the running time would take a lot longer, especially as the input grows. Another example would be if we want to print every single element in the unsorted array.

Consider the code example below:

for (int i = 0; i < arr.length; i++) {
  System.out.print(arr[i])
}

To print every element in an array of size n, every element would have to be visited. The time complexity would be O(n).

If you were to plot the input size n against the number of operations it takes to print every element, a linear function graph is produced. This means that the program would take longer as the size of the input grows.

Therefore, faster processing times are seen for sorted arrays compared to unsorted arrays.