You are working a job where you need to constantly sort lists. your manager says you need to sort one more for you to be done for the day, so you want to pick an array that’s as close to sorted as possible. you define the term k-close to sorted. for the purposes of this problem, we will say that a list of integers is k-close to sorted if every integer is at most k indices away from the index it would be in in a sorted list.

once you know this information, sorting is significantly easier than before. in this problem, you will write a program that takes in a list of integers that is

k-close to sorted and outputs the sorted list. ("sorted" refers to being sorted in ascending order for this problem.)

input will be given as an integer k on its own line, followed by a space separated list of integers. your program should output the sorted list. for example, if you are given the following input:

2

3 2 1 6 4 5 7 9 8 12 10 11

then you should print:

1 2 3 4 5 6 7 8 9 10 11 12

the code for reading input and writing output has been provided in the main class; your job is to implement the sort() method.

restrictions:

• in this problem, your program must have a runtime in o (nlog( where n

is the length of the list and k is the maximum distance between a number’s original position and its position in the sorted list. less efficient answers will receive at most 1/2 credit for this

problem. in particular, algorithms with a runtime in θ(nlog(n)) do not take full advantage of the fact that the list is k-close to sorted. and thus do not represent a complete solution to this problem.

• any data structures and/or algorithms you implement must be implemented by you; you may not, for example, use java’s priorityqueue class or any library sorting methods. answers that use any of java’s data structures other than arrays will not receive credit for this problem.

hint: you might consider using your newfound knowledge of heaps.