Algorithm that mix array respecting certain constraints -

Algorithm that mix array respecting certain constraints -

i've problem:

i must develop algorithm int array , reshuffles elements respecting these constraints:

for each element, must lower neighbors or greater neighbors:

for each x in array a, ( a[x-1]<=a[x] , a[x+1]<=a[x] ) or ( a[x-1]>=a[x] , a[x+1]>=a[x] )

this in theta(n log n) in worst case

i've no thought how this, intuition must similar merge-sort...

sorry mi poor english

sort array

cut in halfs

put elements first half in between elements of sec half

if number of elemnts not move lastly element front

example:

2 3 1 5 7 8 6 4 9

1 2 3 4 5 6 7 8 9

1 5 2 6 3 7 4 8 9

9 1 5 2 6 3 7 4 8

arrays algorithm