Essentially : 1. In pass 1, go through the array and count the number of 1's, 2's and 3's. 2. pass 2 : copy to array the appropriate count of 1's followed by 2's and 3's //Assume that the array has only 1, 2, or 3 as values public void sortInPlace(int[] a) { int oneCount = 0; int twoCount = 0; int threeCount = 0; for(int i = 0; i 0) { a[i] = 1; --oneCount; } else if(twoCount > 0) { a[i] = 2; --twoCount; } else { a[i] = 3; --threeCount; } } } //End of the method sortInplace

This problem boils down to in place exchange of elements. Once you have in place exchange you can use any sorting algorithm. Here is how I will do in place exchange: For e.g. we want to exchange a & b where a = 2, b = 3 a = a + b; // a = 2+ 3 = 5 b = a - b; // b = 5 - 3 = 2 a = a - b ; // a = 5 - 2 = 3 So now a = 3, b = 2. After that we can use selection sort to sort the array.

Two passes First pass: 'push' all the 1s at the start. Second pass: 'push' all the 2s after the 1s from the first pass How to 'push': Keep track of the index_so_far which it should be the next position of the most recent swapped element. Loop over the array and as soon as you see the 1 (or 2 later) element swap it with the one at the index_so_far Code: public static int PushToStart(int[] arr, int value, int start){ int temp = value; int index = start; int sofar = start; for (index=0; index < arr.length; index++){ if (arr[index] == value && sofar < arr.length){ temp = arr[index]; arr[index] = arr[sofar]; arr[sofar] = temp; sofar++ ; } } return sofar; Run this function for value=1 and start=0 get the sofar result and run it once more for value=2 and start=sofar

DNF algorithm is fancy and does it in a single parse but what most people miss is that order is calculated on the operation of "comparison + swapping". While simple algo of counting no of 0s, 1s, and 2s in one parse and then assigning that many no of elements takes two parses, the operations are comparison and assignment. Assignment is cheaper than swapping.

I hate these arbitrary algorithm questions. I don't see what they prove.

Choose the pivot as 1 and call the partition method of quicksort once.