1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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]$. $\endgroup$
    – plop
    Mar 15 at 16:56
  • 2
    $\begingroup$ Have you implemented the accepted answer? Is it correct? $\endgroup$
    – John L.
    Mar 15 at 20:25
  • $\begingroup$ math.stackexchange.com/q/4052385/14578 $\endgroup$
    – D.W.
    Mar 24 at 7:45
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Apr 2 at 10:30
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "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? $\endgroup$
    – user132812
    Mar 15 at 17:14
  • $\begingroup$ @MohammadRostami Please check again if it makes sense now. Point out the errors if any. $\endgroup$ Mar 15 at 18:17
-1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy