Sorting has always been one of the essential operations in computer science, with a plethora of algorithms ranging from the classic QuickSort to the more sophisticated MergeSort. One intriguing problem is sorting `n` numbers that lie in the range `[0, n^2 - 1]` in linear time, which can be achieved using a variant of Counting Sort.

Theoretical Background

Understanding the Problem

The problem at hand is to sort an array of `n` integers where each integer is located within the range `[0, n^2 - 1]`. The standard comparison-based sorting algorithms like QuickSort, MergeSort, or HeapSort have an average time complexity of $O(n \log n)$. However, given this specific scenario, it is possible to achieve the sorting in $O(n)$ time utilizing non-comparison-based sorting.

Why Linear Time Sorting is Possible

The key reason we can achieve $O(n)$ sorting is due to the restriction on the range `[0, n^2 - 1]`. Traditional comparison-based algorithms rely on comparing elements, but by utilizing positional or counting information, such algorithms can perform better for constrained data scenarios. In this context, Counting Sort is adapted but with additional trickery that aligns with the limited range.

Sorting Approach

Core Idea: Radix Sort with Counting Sort

The proposed solution involves a combination of the Counting Sort and Radix Sort algorithm. Given the nature of the input, we can decompose the numbers into two digits based on their range, each being less than `n`.

Steps to Sort:

1. Digit Extraction: Each number in the range `[0, n^2 - 1]` can be viewed as a two-digit number in base `n`:
   • Here, consider `(q, r)` as two parts of a number where:
     • `r` = number % `n`
     • `q` = number // `n`
2. Apply Counting Sort:
   • First, apply Counting Sort on the lower significant digit - `r`.
   • Next, sort the original array on the upper significant digit - `q` using Counting Sort again.
3. Complexity Analysis:
   • Since both digits `q` and `r` are smaller than `n`, sorting them individually uses $O(n)$ operations each.
   • The overall complexity remains $O(n)$ as we perform a constant number of operations per element.

Example Code

Here's a simplistic representation of the algorithm: