Sort an array that contain two sorted array in $O(n)$

Question

Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and $C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in the descending order.

Consider the following example: $B=[2,4,6,8]$ and $C=[9,7,5,1]$. As a result $A=[2,9,7,4,6,5,8,1]$. Interestingly, The instructor said: $A$ can be sorted in $O(n)$. Anyone can give me a hint?

My attempt:

I tried to partition the array $A$ into sorted arrays $B$ and $C$, but I could not do it because my approach encountered counterexamples.

Answer 1

Let $a$ is the first element of $A$. Let $A$ is composed of array $B = (b_{1},\dotsc,b_{n})$ and array $C = (c_{1},\dotsc,c_{n})$. Now, we will partition $A$ into arrays: $B'$ and $C'$ in the increasing and decreasing orders respectively. Following is the process:

1. Let $p$ be a pointer. Initially, $p$ is pointing to $a$. Let $b$ be the element in $A$ next to $a$.
2. There are two possibilities:

Case 1: $a<b$. Then, one of them must be an element of $B$. In this case, if $a$ is greater than the last element of $B'$, add $a$ to $B'$. Move the pointer to $b$ and go to step $1$.

Otherwise, add $a$ to $C'$ and $b$ to $B'$. Move the pointer to the element next to $b$ and go to step $1$.

Case 2: $a>b$. Then, one of them must be an element of $C$. In this case, if $a$ is smaller than the last element of $C'$, add $a$ to $C'$. And, move the pointer to $b$ and go to step $1$.

Otherwise, add $a$ to $B'$ and $b$ to $C'$. Move the pointer to the element next to $b$ and go to step $1$.

The above process produces the array $B'$ in increasing order and $C'$ in decreasing order. However, note that these arrays might not be of the same size.

Correctness: Proof by induction.

Base Step: $A$ is composed of $B$ and $C$. $B'$ and $C'$ are empty right now. In Step $2$, Case 1, we add $a$ to $B'$. If it is indeed an element of $B$ then we are good. If not, then $b \equiv b_{1}$ and we can assume that $A$ is composed of a new array $B' = (a,b_{1},\dotsc,b_{n})$ having elements in the increasing order, and array $C' = C \setminus a$ having elements in the decreasing order. Therefore, adding $a$ to $B'$ is correct.

Similarly, we can prove the correctness of Step $2$, Case $2$. And, the correctness of the further steps follows from the induction step.

---

After obtaining $B'$ and $C'$, you can merge them using merge sort like step in $O(n)$ time.

Answer 2

Here is the natural intuitive way to sort the array. The idea is to keep track of two inserting positions.

0. (Data structure) A node contains a value, a pointer to its previous node, which can be null, and a pointer to its next node, which can be null.

1. Initialize a two-way linked list $L$ with three nodes, the head, a node whose value is the first element of $A$ and the tail. Initialize two pointer $p_1$ and $p_2$, both of which point to the unique node in $L$. It will always be true that $L$ is sorted by its values and $p_1$ is before or the same as $p_2$.

2. Iterate over the remaining element of $A$ in order. Suppose the next element is $a$.

   • If $a \lt p_1.val$, search $L$ element by element backwards starting from $p_1$ until a node with value that is not bigger than $a$ is found or the head of $L$ is reached. Insert a node with value $a$ just after that node. Update $p_1$ to point to the inserted node.
   • If $p1.val \le a\lt p_2.val$, search $L$ element by element backwards starting from $p_2$ until a node with value not bigger than $a$ is found. Insert a node with value $a$ just before that node. Update $p_1$ to point to the inserted node.
   • Otherwise, $a\ge p_2.val$. Search $L$ element by element forwards starting from $p_2$ until a node with value not smaller than $a$ is found or the tail of 𝐿 is reached. Insert a node with value $a$ just before that node. Update $p_2$ to point to the inserted node.

I will leave you to figure out why this is a linear algorithm.