Adaptive Sorting.

A sorting algorithm is called adaptive sort if it takes advantage of previously shorted inputs.The problem with the common sorting algorithms is that they usually don't adapt to the data. Neither quicksort nor merge sort gives optimal results in partially ordered data (quicksort can even give Θ(n2) performance), and adding a preprocessing pass only gets you so far.Adaptive sorting is usually performed by modifying existing sorting algorithms.

This is an attractive algorithm because nearly sorted sequences are common in practice. Thus, the performance of existing sort algorithms can be improved by taking into account the existing order in the input.

A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.

void straightInsertionSort(int *arr, int n){
 *(arr+o) = -someLargeValue;
 for(int j = 2; j < n; j++){
  i = j-1;
  int temp = *(arr+j);
  while(temp < *(arr+i)){
   *(arr+i+1) = *(arr+i);
   i++;
  }
  *(arr+i+1) = temp;
 }
}