Sorting an array in O(N) time

The algorithm you describe is pretty much right, but you made a couple mistakes.

First, you might have to swap multiple times at the same position. Second, if you hit the space you have to put it in the right place. Here is your loop fixed. Note that I stop the iteration one position earlier.

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        if (space==i) {
            // it's the space
            swap(array, i, array.length-1);
            space = array.length-1;
        } else {
            swap(array, array[i]-1, space);
            space = array[i]-1;
            swap(array, space, i);
            space = i;
        }
    }
}

Notice that after we move a number, we always end with space = i, so we'll do the space in the next inner iteration. We can optimize this, ending up with what looks like @OmG's method, except that he missed the while loop too:

swap(array, space, array.length-1);

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        int currentTarget = array[i]-1;
        //move space to current target
        swap(array, currentTarget, array.length-1);
        //move current element to its target
        swap(array, currentTarget, i);
        //put the space back where it belongs
        swap(array, i, array.length-1);
    }
}

It is important to understand why this is still O(n), even though we've added an inner loop: Each iteration of the inner loop fixes the position of exactly one number, after which we will never move that number again. This can happen at most n times, since there are only that many numbers to fix.

Step 1 make a lookup array

You make make an array N+1 long, where each value in the lookup array indicates where it is in the array to be sorted. You can make Lookup[0] refer to where the space is. It will take O(n) time to make such an array. So in the case [7,3,5,4,6,1,2,-1] you make an array [7,5,6,1,3,2,4,0]

Step 2 move the space to start of the array

you can find the current index of the space by lookup[0], if it is already at index 0, then go to the next step, otherwise swap with index 0. You should then update the loop array to reflect the change. ie lookup[value that was at 0] = [where the space started].

Step 3 swap the space with the next element in the array

Now swap the space with 1. You can find it with the lookup array.

Step 4 repeat

Now move the space to index 1 if need, and swap with 2. Then move the space to index 2 and swap with 3. Repeat until it is sorted.

Total time is N to make the lookup array, and 2 swaps for each element, total O(3N).

Using counting sort technique. All the time put the space at the end of the array. You have an array with size N+1. Now, try to read the array from the first place. For example, it is 3. You should put 3 in the 3rd place of the array. To do this, swap the current 3rd value of the array with space, and then swap the first place of the array with the 3rd, and then swap the first with the last item of the array. The latter step will be done to keep the space at the end of the array.

public static int[] arraySort(int[] array){
    int N = array.length - 1;
    for(int i = 0; i < N; i++){
        int currentNum = array[i]-1;
        swap(array, currentNum, N); // swap currentNum-th item with space as the last memebr of the array
        swap(array, i, currentNum); // swap the current item with its place
        swap(array, i, N); // swap the space with the last item.
    }

    return array;
}

public static void swap(int[] arr, int ind1, int ind2){
    int temp = arr[ind2];
    arr[ind2] = arr[ind1];
    arr[ind1] = temp;
}

In the above code, we assume that the location of the space in the start array is in the last. If it is not, you can find it in O(N) and swap it with the last place of the array.