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

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.

• You shouldn't aim to recover $B$ and $C$, since $A=[1,4,2,3]$ could be the result of $B=[1,2]$, $C=[4,3]$ or it could be the result of $B=[1,3]$, $C=[4,2]$. – plop Mar 15 at 16:56
• Have you implemented the accepted answer? Is it correct? – John L. Mar 15 at 20:25
• math.stackexchange.com/q/4052385/14578 – D.W. Mar 24 at 7:45
• To help others shortcut my undulating train of thought: to assess the difficulty to sort such in place, imagine the last element of $B$ smaller than the first of $C$ and both sufficiently interleaved, say, perfectly shuffled. – greybeard Apr 2 at 10:30

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. 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.

• "by choosing the second smallest element" how we can guarantee this be in $O(n)$ for remaining elements? if we repeat it for each element how it be linear? – user132812 Mar 15 at 17:14
• @MohammadRostami Please check again if it makes sense now. Point out the errors if any. – Inuyasha Yagami Mar 15 at 18:17

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

1. (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.

2. 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$$.

3. 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.

• Wait a moment. I need to search from p1.val forwards as well to ensure the linear time-complexity. Updating... – John L. Mar 15 at 19:17
• Maybe I need to keep track of three pointers? In fact, how many pointers are enough? – John L. Mar 15 at 19:26
• Hmm, instead of iterating from left to right, can it be better to iterate from both ends in some way? – John L. Mar 15 at 20:05
• Please do NOT upvote this answer yet! – John L. Mar 15 at 23:22