Here's a solution that I am pretty sure is less than O(n^2). The data are moved only once, but timing the routine suggests that it is O(n log n), but I have no proof of that.
The first and last do-while loops move cycles of data, while the nested do-while loops find the beginning index of a new cycle. Dave int Shuffle( int a[], int N) { int i, j, m, t, u; if( N < 1 ) return 1; if( N == 2 ) return 0; N *= 2; m = N-2; i = j = 1; t = a[j]; do { j = (j+j < N ? j+j : j+j-N+1); u = a[j]; a[j] = t; t = u; m--; } while( j != i ); while( m > 0 ) { do { j = ++i; do j = (j+j < N ? j+j : j+j-N+1); while( j > i ); } while( j != i ); t = a[j]; do { j = (j+j < N ? j+j : j+j-N+1); u = a[j]; a[j] = t; t = u; m--; } while( j != i ); } return 0; } On Aug 6, 12:37 pm, UMESH KUMAR <kumar.umesh...@gmail.com> wrote: > how to sort specific order the given array ,Without using extra memory > > Input:-a1,a2,a3,a4,a5......an,b1,b2,b3,b4,b5..........bn. > > output:-a1,b1,a2,b2,a3,b3,........an.bn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.