Sort an array with only one local variable

Array sorting algorithm question is frequently asked during technical interviews. There are lots of sort algorithms including bubble sort, selection sort, insertion sort, quick sort, merge sort etc. Usually interviewees will be asked to implement sort algorithms. But have you ever been asked to sort an array which you are allowed to define ONLY ONE local variable in your algorithm? 

Bubble sort can be used to do this actually. Normally a bubble sort algorithm may need three local variables : the index variable, the boolean variable to determine whether continue, a temp variable for elements swapping. And a typical bubble sort algorithm implementation looks like.

function bubbleSort(arr) {
	do {
		var isSwapped = false;
		for(var i = 0; i < arr.length - 1; ++i) {
			if(arr[i] > arr[i + 1]) {
				var temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
				isSwapped = true;
 			}
		}
	} while (isSwapped);	
}

In this implementation, the three local variables are i, isSwapped and temp. To allow only one local variable, isSwapped and temp need to be eliminated. 

First considering about the temp variable for element swapping, there is method to eliminate temp by using XOR operator.  In simple, the code for swapping using XOR is

var x = 5, y = 6;
x = x^y;
y = x^y;
x = x^y;

Next trying to remove the boolean variable -- isSwapped. Actually this variable is just to indicate whether all elements in the array are in order. The index variable can be used to substitute this boolean variable. Basically we just need to check whether the index is less than the array length - 1 after each swap and start the sorting all over again. The array is sorted until the index is equal to array length - 1.

With above two tricks, there is only one local variable existing and the implementation looks like.

function bubbleSort(arr) {
	do {
		for(var i = 0; i < arr.length - 1; ++i) {
			if(arr[i] > arr[i + 1]) {
				arr[i] = arr[i] ^ arr[i + 1];
				arr[i + 1] = arr[i] ^ arr[i + 1];
				arr[i] = arr[i] ^ arr[i + 1];
				break;
 			}
		}
	} while (i < arr.length - 1);	
}

In fact, there is a more elegant method where only one for loop is needed. It has similar logic as above but with the do while loop eliminated. It will reset the index to 0 after each swap and exit when the index is equal to array length - 1.

function bubbleSort(arr) {
	for(var i = 0; i < arr.length - 1; ++i) {
		if(arr[i] > arr[i + 1]) {
			arr[i] = arr[i] ^ arr[i + 1];
			arr[i + 1] = arr[i] ^ arr[i + 1];
			arr[i] = arr[i] ^ arr[i + 1];
			i = -1;
		}
	}
}

Happy coding and have fun!