If you want O(n) time and no extra memory usage (since array was specified), use the algorithm from Jon Bentley's book, "Programming Pearls 2nd Edition". It swaps all the elements twice. Not as fast as using linked lists but uses less memory and is conceptually simple.

shiftArray( theArray, M ):    size = len( theArray )    assert( size > M )    reverseArray( theArray, 0, size - 1 )    reverseArray( theArray, 0, M - 1 )    reverseArray( theArray, M, size - 1 )

reverseArray( anArray, startIndex, endIndex ) reverses the order of elements from startIndex to endIndex, inclusive.

Optimal solution

Question asked for fastest. Reversing three times is simplest but moves every element exactly twice, takes O(N) time and O(1) space. It is possible to circle shift an array moving each element exactly once also in O(N) time and O(1) space.

Idea

We can circle shift an array of length N=9 by M=1 with one cycle:

tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;

And if N=9, M=3 we can circle shift with three cycles:

1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

Note each element is read once and written once.

Diagram of shifting N=9, M=3

The first cycle is show in black with numbers indicating the order of operations. The second and third cycles are shown in grey.

The number of cycles required is the Greatest Common Divisor (GCD) of N and M. If the GCD is 3, we start a cycle at each of {0,1,2}. Calculating the GCD is fast with the binary GCD algorithm.

Example code:

// n is length(arr)// shift is how many place to cycle shift leftvoid cycle_shift_left(int arr[], int n, int shift) {  int i, j, k, tmp;  if(n <= 1 || shift == 0) return;  shift = shift % n; // make sure shift isn't >n  int gcd = calc_GCD(n, shift);  for(i = 0; i < gcd; i++) {    // start cycle at i    tmp = arr[i];    for(j = i; 1; j = k) {      k = j+shift;      if(k >= n) k -= n; // wrap around if we go outside array      if(k == i) break; // end of cycle      arr[j] = arr[k];    }    arr[j] = tmp;  }}

Code in C for any array type:

// circle shift an array left (towards index zero)// - ptr    array to shift// - n      number of elements// - es     size of elements in bytes// - shift  number of places to shift leftvoid array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift){  char *ptr = (char*)_ptr;  if(n <= 1 || !shift) return; // cannot mod by zero  shift = shift % n; // shift cannot be greater than n  // Using GCD  size_t i, j, k, gcd = calc_GCD(n, shift);  char tmp[es];  // i is initial starting position  // Copy from k -> j, stop if k == i, since arr[i] already overwritten  for(i = 0; i < gcd; i++) {    memcpy(tmp, ptr+es*i, es); // tmp = arr[i]    for(j = i; 1; j = k) {      k = j+shift;      if(k >= n) k -= n;      if(k == i) break;      memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];    }    memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;  }}// cycle right shifts away from zerovoid array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift){  if(!n || !shift) return; // cannot mod by zero  shift = shift % n; // shift cannot be greater than n  // cycle right by `s` is equivalent to cycle left by `n - s`  array_cycle_left(_ptr, n, es, n - shift);}// Get Greatest Common Divisor using binary GCD algorithm// http://en.wikipedia.org/wiki/Binary_GCD_algorithmunsigned int calc_GCD(unsigned int a, unsigned int b){  unsigned int shift, tmp;  if(a == 0) return b;  if(b == 0) return a;  // Find power of two divisor  for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }  // Remove remaining factors of two from a - they are not common  while((a & 1) == 0) a >>= 1;  do  {    // Remove remaining factors of two from b - they are not common    while((b & 1) == 0) b >>= 1;    if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b    b = b - a;  }  while(b != 0);  return a << shift;}

Edit: This algorithm may also have better performance vs array reversal (when N is large and M is small) due to cache locality, since we are looping over the array in small steps.

Final note: if your array is small, triple reverse is simple. If you have a large array, it is worth the overhead of working out the GCD to reduce the number of moves by a factor of 2.Ref: http://www.geeksforgeeks.org/array-rotation/

It's just a matter of representation. Keep the current index as an integer variable and when traversing the array use modulo operator to know when to wrap around. Shifting is then only changing the value of the current index, wrapping it around the size of the array. This is of course O(1).

For example:

int index = 0;Array a = new Array[SIZE];get_next_element() {    index = (index + 1) % SIZE;     return a[index];}shift(int how_many) {    index = (index+how_many) % SIZE;}