Sort a nearly sorted (or K sorted) array

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.

For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.

http://www.geeksforgeeks.org/nearly-sorted-algorithm/

Question 2:
Sort an almost sorted array where only two elements are swapped
Given an almost sorted array where only two elements are swapped, how to sort the array efficiently?

Example

Input:  arr[] = {10, 20, 60, 40, 50, 30}
// 30 and 60 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}

Input:  arr[] = {10, 20, 40, 30, 50, 60}
// 30 and 40 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}

Input:   arr[] = {1, 5, 3}
// 3 and 5 are swapped
Output:  arr[] = {1, 3, 5}
Expected time complexity is O(n) and only one swap operation to fix the array.'

http://www.geeksforgeeks.org/sort-an-almost-sorted-array-where-only-two-elements-are-swapped/