Please help with coding of this cocktail sort.

Cocktail sort should be inplace and stable. It should have a worst case running time of O(n 2 ) and a best case running time of O(n). Note: Implement cocktail sort with the optimization where it utilizes the last swapped index. Remembering where you last swapped will enable some optimization for cocktail sort. For example, traversing the array from smaller indices to larger indices, if you remember the index of your last swap, you know after that index, there are only the largest elements in order. Therefore, on the next traversal down the array, you start at the last swapped index, and on the next traversal up the array, you stop at the last swapped index. Make sure that both on the way up and on the way down, you only look at the indices that you do not know are sorted. Do not make extra comparisons.

/** * Implement cocktail sort. * * It should be: * in-place * stable * * Have a worst case running time of: * O(n^2) * * And a best case running time of: * O(n) * * You may assume that the array doesn't contain any null elements. * * NOTE: See pdf for last swapped optimization for cocktail sort. You * MUST implement cocktail sort with this optimization * * @throws IllegalArgumentException if the array or comparator is null * @param data type to sort * @param arr the array that must be sorted after the method runs * @param comparator the Comparator used to compare the data in arr */ public static void cocktailSort(T[] arr, Comparator comparator) {

}