WAP To Implement The Bitonic Sorting Can Be extended to K-tonic Sorting

public class BitonicSorterForArbitraryN
{
private static int[] a;
private final static boolean ASCENDING=true; // sorting direction

public static void sort(int[] ar)
{
a=ar;
bitonicSort(0, a.length, ASCENDING);
}

private static void bitonicSort(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, !dir);
bitonicSort(lo+m, n-m, dir);
bitonicMerge(lo, n, dir);
}
}

private static void bitonicMerge(int lo, int n, boolean dir)
{
if (n>1)
{
int m=greatestPowerOfTwoLessThan(n);
for (int i=lo; i compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, n-m, dir);
}
}

private static void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}

private static void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}

private static int greatestPowerOfTwoLessThan(int n)
{
int k=1;
while (k k=k<<1;
return k>>1;
}

public static void main(String ar[])
{
int a[]={1,2,3,4,5,9,8,7,6};
sort(a);
for(int i=0;i<9;i++)
System.out.println(a[i]);
}

}

The new sorting network for arbitrary n can be embedded into an original bitonic sorting network for 2k. Therefore, it also consists of ceiling 1log(n)ceiling 2 · (ceiling 1log(n)ceiling 2 + 1) / 2 stages. Each stage consists of at most n/2 comparators. This results in a complexity of O(n log(n)2) comparators, just as the original bitonic sorting network.


Time Complexity O(n(logn)^2))
Space O(1)