Creating quicksort without recursion and stack

Question

I have a task to write quicksort (on only posivite numbers) algorythm in Java (I can't use any imports but Scanner) but without recursion and without stack.
I have two question about it :

1. I do understeand iterative quicksort with stack and recursive version but i cannot imagine how to do it without it. I have heard about some 'in place' implementation but i dont really get it - is it solution for my problem?
   I would appreciate if anyone could show me a way to do it ( dont post implementation if you can, I just want to understeand it not copy someone's code) or recommend some book where I can find it ( or some similar problem ).

2. Is implementing sort by insertion for some small arrays a good idea? If so how big should be N in this code :

   if (arraySize < N)
       insertionSort
   else 
       quickSort
   fi
   

Answer 1

Apparently my task was to find only posivite numbers, here is my solution:

public static void quickSort(final int size) {
    int l = 0;
    int r = size - 1;
    int q, i = 0;
    int tmpr = r;
    while (true) {
        i--;
        while (l < tmpr) {
            q = partition(l, tmpr);
            arr[tmpr] = -arr[tmpr];
            tmpr = q - 1;
            ++i;
        }
        if (i < 0)
            break;
        l++;
        tmpr = findNextR(l, size);
        arr[tmpr] = -arr[tmpr];
    }
}

private static int findNextR(final int l, final int size) {
    for (int i = l; i < size; ++i) {
        if (arr[i] < 0)
            return i;
    }
    return size - 1;
}

private static int partition(int l, int r) {
    long pivot = arr[(l + r) / 2];
    while (l <= r) {
        while (arr[r] > pivot)
            r--;
        while (arr[l] < pivot)
            l++;
        if (l <= r) {
            long tmp = arr[r];
            arr[r] = arr[l];
            arr[l] = tmp;
            l++;
            r--;
        }
    }
    return l;
}

My array to sort is an static array in my class. It is based on finding and creating negative numbers. Partition is created by using middle element in array but using median is also good (it depends on array). I hope someone will find this usefull.

Answer 2

Just as a reference the Java8 implementation of Arrays.sort(int[]) uses a threshold of 47, anything less than that is sorted using insertion. Their quick sort implementation is however very complex with some initial overhead, so look upon 47 as an upper limit.