Processing a sorted array is often faster than an unsorted array because sorted arrays enable more efficient algorithms and optimizations. For example, operations like searching, range queries, and duplicate removal can take advantage of the order in the sorted data.

Unsorted Array Approach (Brute Force)

For an unsorted array, the brute force approach would be to check all possible pairs, resulting in a time complexity of O(n2)O(n^2)O(n2).

public class UnsortedArrayExample {
    public static boolean hasPairWithSum(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    return true; // Pair found
                }
            }
        }
        return false; // No pair found
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 4, 1, 5};
        int target = 9;

        System.out.println(hasPairWithSum(arr, target)); // Output: true (7 + 2 = 9)
    }
}

Sorted Array Approach (Two Pointers)

For a sorted array, the two-pointer technique can solve the problem in O(n)O(n)O(n) time by leveraging the sorted order.

import java.util.Arrays;

public class SortedArrayExample {
    public static boolean hasPairWithSum(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) {
                return true; // Pair found
            } else if (sum < target) {
                left++; // Increase the smaller value
            } else {
                right--; // Decrease the larger value
            }
        }
        return false; // No pair found
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 4, 1, 5};
        Arrays.sort(arr); // Sort the array: {1, 2, 4, 5, 7}
        int target = 9;

        System.out.println(hasPairWithSum(arr, target)); // Output: true (2 + 7 = 9)
    }
}

Comparison

Key Insights

1. Sorting adds an initial overhead (O(nlog⁡n)O(n \log n)O(nlogn)), but once sorted, operations like searching and summing become faster.
2. Sorting is especially beneficial when the array is processed multiple times, as the cost of sorting is amortized.
3. Techniques like binary search or two-pointer methods are directly enabled by the sorted order, providing significant performance boosts.