Closer sort

• Sort an almost sorted array

# Python program for the above approach
def sort(array, l, h, k):
	mid = l + (h - l) // 2 # Choose middle element as pivot
	i = max(l, mid - k)
	j = i
	end = min(mid + k, h) # Set appropriate range
	array[mid], array[end] = array[end], array[mid] # Swap middle and last element to avoid extra complications
	while j < end:
		if array[j] < array[end]:
			array[i], array[j] = array[j], array[i]
			i += 1
		j += 1
	array[end], array[i] = array[i], array[end]
	return i
 
def ksorter(array, l, h, k):
	if l < h:
		q = sort(array, l, h, k)
		ksorter(array, l, q - 1, k)
		ksorter(array, q + 1, h, k)
 
# Driver code
array = [3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12]
k = 3
print("Array before K sort")
print(array)
 
# Function call
ksorter(array, 0, len(array) - 1, k)
print("Array after K sort")
print(array)