QuickSort an array without modifying it (may not use a temporary array) in C++ -

normally never ask school exercise on stackoverflow think want impossible without using temporary array or modifying array.

what want is:

1. quicksort function should recursive

2. it should sort(that sorting algorithms lol) should leave array intact,

3. may not use temporary array

4. and has return sorted list in linkedlist format.

5. function should this:

linkedlist *quicksort(int *array, int startposition, int endposition)

returning linkedlist easy, sorting easy without modyfying in everystep of algorithm? dont think so.

i not saying please send me solution. want answer this, not impossible?

edit: "leaving array intact" teacher meant "dont change size of array, can modify order of array", problem solved

i check 1 of answers make tag question solved.

to answer question directly: quick sort can done in place (without temporary storage areas.)

since don't want complete homework directly :) here resource going.

see second algorithm @ http://rosettacode.org/wiki/sorting_algorithms/quicksort