This assignment is meant to be done in Java. Please make sure that it sorts in O(nk) time. Thank you.

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(nk) 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 Input arr[] -6, 5, 3, 2, 8, 10, 9) Output arr[] (2, 3, 5, 6, 8, 9, 10) Input arrl] (10, 9, 8, 7, 4, 7, 60, 50) k 3 output: arrt (4, 7, 8, 9, 10, se, 6o, 7e) 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(nk) 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 Input arr[] -6, 5, 3, 2, 8, 10, 9) Output arr[] (2, 3, 5, 6, 8, 9, 10) Input arrl] (10, 9, 8, 7, 4, 7, 60, 50) k 3 output: arrt (4, 7, 8, 9, 10, se, 6o, 7e)