Linear-Time Algorithm for Rank-Based Array Partitioning

Given an array A of n distinct numbers and two positive integers k and l where 1 < k < l < n, we need to:

1. Rearrange the array so elements with ranks between k and l are placed in positions k through l
2. Ensure the rearrangement happens in-place
3. Complete the task in linear time

For example, if we have A = [5,8,1,6,9,2,3,7,4], k = 4, and l = 7, a valid result might be:

• [1,2,3,6,4,5,7,8,9] or
• [1,2,3,6,5,7,4,8,9]

Solution

The key insight is that we can adapt the quickselect approach to partition our array around two ranks

PARTITION-BY-RANKS(A, n, k, l)
    # Step 1: Partition around rank k
    k_val = R-SELECT(A, 1, n, k)
    i = 1
    j = n
    while i < j
        while A[i] < k_val and i < n
            i = i + 1
        while A[j] > k_val and j > 1
            j = j - 1
        if i < j
            swap A[i] with A[j]
    
    # Step 2: Partition around rank l
    l_val = R-SELECT(A, k, n, l)
    i = k
    j = n
    while i < j
        while A[i] ≤ l_val and i < n
            i = i + 1
        while A[j] > l_val and j > k
            j = j - 1
        if i < j
            swap A[i] with A[j]
    
    return A

Breaking Down the Algorithm

Step 1: Finding and Partitioning Around Rank k

The first phase uses R-SELECT to find the kth smallest element. This becomes our first partition point. We then rearrange the array so that:

• Elements with ranks < k move to the left side
• Elements with ranks ≥ k move to the right side

This step ensures that positions 1 through k-1 contain exactly the elements they should.

Step 2: Finding and Partitioning Around Rank l

The second phase finds the lth smallest element using R-SELECT. We then partition the remaining array (from position k onward) so that:

• Elements with ranks ≤ l stay in the middle section
• Elements with ranks > l move to the right side

This naturally places elements with ranks between k and l into positions k through l.

Time Complexity Analysis

Let’s break down the time complexity of each component:

1. First R-SELECT call: O(n) expected time
2. First partitioning phase: O(n)
3. Second R-SELECT call: O(n) expected time
4. Second partitioning phase: O(n)

The total expected time complexity is O(n), making this a linear-time algorithm. It’s worth noting that we achieve this without requiring any additional space beyond a few variables, making it truly in-place.

Space Complexity

The algorithm uses only O(1) extra space for:

• Variables for loop counters and temporary storage during swaps
• Recursion stack space for R-SELECT (which is O(log n) expected)