This video explains a very important programming interview problem which is to sort a nearly sorted array or a k sorted array.I have explained 3 approaches for solving this problem.In this problem, given an array we need to sort it.But the array has special property of being K-sorted, which means that each element is atmost K away from its actual position in a sorted array.I have shown how to make use of this property and solve the entire problem efficiently.The first method is by using simple sorting which takes O(NlogN) time.The second method is by using insertion sort and the third method is by using Heap.I have also shown comparision between all these methods.Code for both insertion sort and heap are explained at the end of the video.

CODE: Insertion Sort

/* Function to sort an array using insertion sort*/
void insertionSort(int A[], int size) 
{ 
int i, key, j; 
for (i = 1; i < size; i++) 
{ 
	key = A[i]; 
	j = i-1; 

	/* Move elements of A[0..i-1], that are greater than key, to one 
		position ahead of their current position. 
		This loop will run at most k times */
	while (j >= 0 && A[j] > key) 
	{ 
		A[j+1] = A[j]; 
		j = j-1; 
	} 
	A[j+1] = key; 
} 
}

CODE: Using Max_Heap

// A STL based C++ program to sort a nearly sorted array. 
#include <bits/stdc++.h> 
using namespace std; 

// Given an array of size n, where every element 
// is k away from its target position, sorts the 
// array in O(nLogk) time. 
int sortK(int arr[], int n, int k) 
{ 
	// Insert first k+1 items in a priority queue (or min heap) 
	//(A O(k) operation). We assume, k < n. 
	priority_queue<int, vector<int>, greater<int> > pq(arr, arr + k + 1); 

	// i is index for remaining elements in arr[] and index 
	// is target index of for current minimum element in 
	// Min Heapm 'hp'. 
	int index = 0; 
	for (int i = k + 1; i < n; i++) { 
		arr[index++] = pq.top(); 
		pq.pop(); 
		pq.push(arr[i]); 
	} 

	while (pq.empty() == false) { 
		arr[index++] = pq.top(); 
		pq.pop(); 
	} 
} 

// A utility function to print array elements 
void printArray(int arr[], int size) 
{ 
	for (int i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

// Driver program to test above functions 
int main() 
{ 
	int k = 3; 
	int arr[] = { 2, 6, 3, 12, 56, 8 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	sortK(arr, n, k); 

	cout << "Following is sorted array" << endl; 
	printArray(arr, n); 

	return 0; 
}