Sort an array which is first increasing then decreasing

Question

Given an array which is having elements which are in increasing order till a max value and then numbers in decreasing order.

Eg. int a[] = { 10, 12, 14, 16, 15, 13, 11}.

How can this array be sorted efficiently?

The array needs to be sorted in-place.

Answer 1

Find the maximum value and then reverse the array up to that value. Then apply a merge on the two subarrays - first one that contains the maximum value and than the remaining array. This will have linear computational complexity and will require linear additional memory.

In your case:

a[] = { 10, 12, 14, 16, 15, 13, 11} => {10,12,14,16}, {15,13,11}

=> reverse(linear, in-place) =>

{16,14,12,10}, {15,13,11}

=> merge(linear, additional linear memory) =>

{16,15,14,13,12,11,10}

EDIT: For how to merge two arrays in place with no additional memory have a look at this answer

Answer 2

My solution:

1. Take 2 pointers start of array and end of array.

2. Into result array write a min(or max if you need sort in descending) value from both pointers, and shift pointer to 1 position (start pointer +1 position and end pointer -1 position

3. Repeat till start pointer will be placed after end pointer.

Complexity of solution is O(N). Required memory is O(N)

Pseudocode:

function Sort(a)
{
  startPointer = 0;
  endPointer = a.length-1;
  result = new Array of size a.length
  while (startPointer <= endPointer)
  {
    var newValue;
    if (a[startPointer] < a[endPointer])
    {
      newValue = a[startPointer];
      startPointer +1
    }
    else
    {
      newValue = a[endPointer];
      endPointer -1
    }
    result[a.length - startPointer - endPointer] = newValue;
  }

  return result;
}

Solution for updated question:

As solution usde partil sorting of first part of array.

Pointers on (10 and 11) {10, 12, 14, 16, 15, 13, 11}

Pointers on (12 and 11) Swap 12 and 11 {10, 11, 14, 16, 15, 13, 12}

Pointers on (14 and 12) Swap 14 and 12 {10, 11, 12, 16, 15, 13, 14} // Move pointer from 14 to 13 a it lesser.

Now we have sorted {10, 11, 12} and sub problem for {16, 15, 13, 14} (N for sub problem decreased twicely)

Complexity for this algorithm is: O(N) + (N/2) + O(N/4) + ... totally is O(N)

Image for better illustration:

Answer 3

Use the property of the question.

You need not sort the array that is already sorted. Find the point where the slope changes and then use a suitable algorithm to get a complete sorted array.

You could consider implementing a bitonic sorter which uses this property efficiently.