Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

Question

Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time?

For example, let's say that $A = [4, 11, 6, 2, 9, 7]$. Then, one of the required sequences can be $[2, 7, 11]$, which is the sorted version of the subsequence $[11, 2, 7]$. Your strategy can give any such subsequence in a sorted order.

Yes, I think that it's 99.99% impossible. But, I don't know for sure. Can anyone show that there cannot exist such a strategy or prove otherwise?

Answer 1

It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time.

Consider the following sorting algorithm:

def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

In result, the running time is $O(n + \frac n2 + \frac n4 + ...) = O(n)$, which violates a well-known lower bound for sorting.