Stable sort an array with k distinct elements, each appearing double the times the previous one appears

Question

I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague.

Here's the problem:

Given an array with $k$ distinct elements, it is known that the smallest element appears once, the 2nd smallest element appears twice, the 3rd smallest element appears 4 times, the 4th smallest appears 8 times, and so on until the $k$-th smallest element, which appears exactly $2^{k-1}$ times.

Marking the size of the array as $n=2^k-1$, suggest an algorithm to stable sort the array in $O(n)$, provide explanation for the algorithm.

The second path of thought I had was making a new array sized $\log(n)$ with a queue in each cell, thus repeating elements keep their order.

However, the best algorithm I came of is doing this is $O(nk)=O(n\log n)$ time, which seems pretty legit to a sorting algorithm without a given range(such as in bucketsort). Yet the problem demands $O(n)$.

Answer 1

Copy the elements into a temporary array. As long as the temporary array isn't empty, repeat this:

1. Find the majority value in the temporary array (e.g., using Boyer-Moore (or, as Rainer's answer reminds, simply max in our case, but I'll keep majority now)).
2. Copy the majority elements backwards into the original array.
3. Remove the majority elements from the temporary array.

Python implementation including test (Try it online!):

def sort(xs):
    tmp = xs[:]
    i = len(xs)
    while tmp:
        m = majority(tmp)
        for x in reversed(tmp):
            if x == m:
                i -= 1
                xs[i] = x
        tmp = [x for x in tmp if x != m]

def majority(xs):
    leader = None
    lead = 0
    for x in xs:
        if not lead:
            leader = x
            lead = 1
        elif x == leader:
            lead += 1
        else:
            lead -= 1
    return leader

from random import sample, shuffle
k = 15
xs = sorted(sample(range(1000), k))
xs = [[x] for i, x in enumerate(xs) for x in [x] * 2**i]
shuffle(xs)
expect = sorted(xs)
sort(xs)
print(xs == expect)
print(all(x is e for x, e in zip(xs, expect)))

For the curious reading the test code: I wrap each number in a list so that I get distinct (but equal-valued) objects. That allows testing the stability, which I do at the end with the identity checks using is. Note that Python's own sorted is stable, so I use that to compute the expected order.

Answer 2

Find the maximum element, then partition the array into two buckets, smaller and equals. Apply the algorithm recursively to the smaller bucket. Here is an example implementation in Python:

def quicksort(data):
    '''stable out-of-place quicksort with maximum element for pivot'''
    if not data:
        return []
    pivot = max(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    return quicksort(smaller) + equals

If the majority element is not necessarily the largest one, you have to expand it into a full quicksort and use the Boyer-Moore majority algorithm to find the pivot, like this:

def quicksort(data):
    '''stable out-of-place quicksort with majority element for pivot'''
    if not data:
        return []
    pivot = majority(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    greater = [x for x in data if x > pivot]
    return quicksort(smaller) + equals + quicksort(greater)

Runtime complexity is linear because half of the items fall into the equals bucket, where no recursive sort is applied. Both algorithms produce a correct and stable sort on any input, but linear runtime complexity is only guaranteed if a majority element exists and is chosen for pivot.

Answer 3

Consider a version of Mergesort that returns an array of lists. Each list in the array groups all element with the same value (and stores them in the same order as they appear in the original array).

Clearly each array has at most $k$ elements. Moreover, if we are given two sorted arrays, each of which stores $m$ elements overall in its lists, we can merge them in time $O(\min\{m,k\}) = O(\min\{m, \log n\})$.

The running time of the algorithm is therefore described by the recurrence:

$$T(m) = 2T(m/2) + O(\min\{m,\log n\}),$$ which has solution $T(n) = O(n)$.

Answer 4

The main idea is to sort it from the largest element that basically will appear $n/2$ times, the second largest will appear $n/4$ and continues on until the smallest.

For example after sorting this array $[8,3,2,8,8,8,3]$ it will look like that $[2,3,3,8,8,8,8]$ (where k=3). In order to take out the all appearances of 8 it will cost $O(n)$ (one iteration for finding who the largest is, and second to move all of his appearances to be between $n/2_{th}$ and the $n_{th}$ places).

Now we have half sorted array $[3,2,3,8,8,8,8]$ so we will need to deal with the remaining half array $[3,2,3]$ so basically we are facing now the same problem but with k=2.

Therefore we will use recursive solution:

$T(n)=T(\frac{n}{2})+O(n)$ By using the master theorem the answer is $O(n)$

For better understanding it really close to merge-sort just with sorting half array every time.