Linear Sort in Java: Guide for Beginners

Linear sort algorithms sort data in O(n) time — faster than comparison-based sorts like quicksort (O(n log n)) by exploiting the structure of the data rather than comparing elements. In Java, counting sort and radix sort are the two most commonly used linear sorting algorithms for appropriate data types.

What Is Linear Sorting?

Linear sorting achieves O(n) time complexity by not performing comparisons between elements. Instead, it uses information about the data’s structure — its range of values (counting sort) or its digit-by-digit representation (radix sort) — to place elements directly into their correct position. The trade-off is that these algorithms work only on specific data types: counting sort requires integers in a known range, radix sort works on integers or fixed-length strings.

Counting Sort in Java

public static int[] countingSort(int[] arr, int maxValue) {
    int[] count = new int[maxValue + 1];
    for (int num : arr) count[num]++;
    
    int[] sorted = new int[arr.length];
    int idx = 0;
    for (int i = 0; i <= maxValue; i++) {
        while (count[i]-- > 0) sorted[idx++] = i;
    }
    return sorted;
}

Counting sort is ideal for sorting arrays of integers with a known, limited range — for example, exam scores (0-100), ages (0-120), or character ASCII values (0-127). Time complexity: O(n + k) where k is the range of values. Space complexity: O(k).

When to Use Linear Sort vs Comparison Sort in Java

Use counting sort or radix sort when: you are sorting integers or fixed-length strings, the range of values is known and not much larger than the array size, and performance is critical. Use Java’s built-in Arrays.sort() (which uses TimSort, an optimized comparison sort) for general-purpose sorting, objects, or when data characteristics are unknown.

Frequently Asked Questions

Is Arrays.sort() in Java a linear sort?

No. Java’s Arrays.sort() uses TimSort (a hybrid merge sort / insertion sort) with O(n log n) time complexity. For linear sorting in Java, you need to implement counting sort or radix sort manually, as these are not included in the standard library.