Circular Sort: an improved insertion sort algorithm

Insertion sort is great, it is in place, online, and stable, usually faster than selection sort and bubble sort.
Selection sort is the one of the sort algorithm using the least number of swaps, which is usually when swap in memory operation is expensive such as in flash.

In reality if the input is partially sorted or input size is small, insertion sort is quicker than quick sort.
When the input size is small, some of the fast sorting algorithms implementation, e.g. in Java, when using quick sort, heap sort, merge sort will fall back to insertion sort. The problem with insertion sort is the numbers of potential moves or shifts in array could be O(n^2), e.g. if the array is in reverse order.

Circular sort is an improved version of insertion sort which using circular buffer or circular array to solve the insertion sort problem.

I strongly recommend you to read the wiki page about circular buffer (cb), http://en.wikipedia.org/wiki/Circular_buffer.

A simple CB implementation involves a start, end pointer and buffer size parameter. An elegant CB implementation using mirroring algorithm.

Here is the code doing circular sort, which essentially an insertion sort, but can append to front and end in O(1) time thanks to the circular buffer.

public static int[] circularSort(int[] nums){

int len = nums.length;

int[] cb = new int[len];

cb[len/2] = nums[0];

int start = len/2, end = len/2;

for(int i=1; i<len; i++){

//if nums[i] is the smallest, append to the front

if(nums[i]<=cb[start]){

start = start == 0? len-1:start-1;

cb[start] = nums[i];

//if nums[i] is the biggest, append to the end

}else if(nums[i]>=cb[end]){

end = end == len-1? 0 : end+1;

cb[end] = nums[i];

}else{

//if nums[i] falls into first half

if(nums[i]<cb[len/2]){

start = start == 0? len-1:start-1;

int p = start;

//shift the first half to left circularly 

while(cb[p]<nums[i]){

int next = p-1>=0? p-1: len-1;

cb[next] = cb[p];

p++;

}

cb[p] = nums[i];

//if nums[i] falls into second half

}else{

end = end == len-1? 0 : end+1;

int p = end;

//shift the second half to right circularly

while(cb[p]>nums[i]){

int next = p+1<len? p+1: 0;

cb[next] = cb[p];

p--;

}

cb[p] = nums[i];

}

}

}

return cb;

}

Algorithm analysis: 

The best case is when the input is already in increasing or decreasing order, because only append or prepend operations are required.  O(N).

For random order input data is handled much better than Insertion Sort, because the number of moves is less. 

Potential improvements or modifications:
1. using binary search to find the position for nuns[i] in either half of the buffer
2. using bigger buffer like 2*N-1 so we don't need to wrap-around operation in circular buffer.
3. doing the sort in place which is the cycle sort implementation.