# What is an ordered array? [duplicate]

I am not able to find a clear explanation about Ordered Arrays. All I know is

The array is 1-ordered it is in the usual order. (For the 1st must be less than the 2nd which in turn must be less than the 3rd which ... which must be less than the $n$th.)

But what is 2-ordered, 3-ordered... so on array?

Can someone guide me?

## marked as duplicate by David Richerby, jmite, Yuval Filmus, Luke Mathieson, hengxinDec 28 '14 at 5:26

Borrowing the definition from Gaurang Tandon's question:

An array $A[1...n]$ is said to be k-ordered if $$A[i - k] \leq A[i] \leq A[i + k]$$ for all $i$ such that $k < i \leq n - k$.

For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.

I must also say that I've never seen a similar definition before (and I find it to be quite un-useful, but maybe it is important somewhere).

Another definition I have seen, extends the ordering to $k$-dimensional objects. For instance, with two dimensions:

Given vectors $v=(v_1,v_2)$ and $u=(u_1,u_2)$, we say that $v>u$ in a 2-ordering if
$$v_1 > u_1$$ or if $$v_1=u_1 \text{ and } v_2>u_2$$

Then, an array of vectors $v[1...n]$ is $2$-ordered if for every $i$, $v[i]<v[i+1]$ via the above 2-ordering.