# Program to Find the Smallest Unsorted Subarray such that Sorting it Makes Whole Array Sorted

• Write a program in C to find smallest unsorted array such that sorting this array makes whole array sorted.

Given an integer array of size N, we have to find smallest unsorted subarray, sorting which will make whole of input array sorted. If input array is already sorted then no sub subarray exists whereas if array is sorted in decreasing order then we have to sort whole input array. For Example :

```
Input Array : [1 3 4 6 5 2 11 7 10 14 15 16]
Unsorted sub-Array is from index 1 to 8

Input Array : [1 2 3 4 7 6 5 8 9 10]
Unsorted sub-Array is from index 4 to 6
```

Let inputArray be a sorted integer array of size N.
Algorithm to find smallest unsorted subarray.
• Traverse inputArray from index 0 to N-1 and find first element which is greater than it's next element. Let this index be leftIndex (inputArray[leftIndex] > inputArray[leftIndex+1]).
• If leftIndex >= N-1, then whole array is already sorted.
• Traverse inputArray from index N-1 to 0 and find first element which is smaller than it's next element. Let this index be rightIndex (inputArray[rightIndex] < inputArray[rightIndex -1])
• Now find the minimum and maximum element of subarray from index leftIndex to rightIndex. Let it be min and max.
• Traverse inputArray from index N-1 to rightIndex and find first element smaller than max. Let this index be rightMostIndex.
• Traverse inputArray from index 0 to leftIndex and find first element larger than min. Let this index be leftMostIndex.
• Required subarray is from index rightMostIndex to leftMostIndex.

## C program to find smallest unsorted subarray to make whole array sorted

```#include <stdio.h>

void findUnsortedSubArray(int *array, int size) {
int i, left, right, min, max;

/* traverse from left to right and find first
element which is greater than next element */
for(left = 0; left < size-1; left++) {
if (array[left] > array[left+1])
break;
}
/* If left == size-1, then whole array is already sorted */
if(left == size-1) {
return;
}

/* traverse from right to left and find first
element which is smaller than next element */
for(right = size-1; right > 0; right--){
if(array[right] < array[right-1])
break;
}

/* Now find the maximum and minimum element
of sub array from index left to right */
max = array[left];
min = array[right];
for(i = left+1; i <= right; i++) {
if(array[i] < min)
min = array[i];
if(array[i] > max)
max = array[i];
}

/* Traverse from right to left and find
first element which is smaller than max */
for(i = size-1; i >= right+1; i--) {
if(array[i] < max) {
right = i;
break;
}
}

/* Traverse from left to right and find
first element which is greater than min */
for(i = 0; i < left; i++) {
if(array[i] > min) {
left = i;
break;
}
}

printf("\nUnsorted sub-Array is from index %d to %d", left, right);
return;
}

int main(){
int array = {1, 3, 4, 6, 5, 2, 11, 7, 10, 14, 15, 16};
int i;

for(i = 0; i < 12; i++){
printf("%d ", array[i]);
}

findUnsortedSubArray(array, 12);

return 0;
}
```
Output
```1 3 4 6 5 2 11 7 10 14 15 16
Unsorted sub-Array is from index 1 to 8
```