In-place Sorting

[sumithra]

Hi,

I am not sure what exactly "sorting in-place" means, although I am aware of the definition that an in-place algorithm uses constant amount of space for variables while doing the sorting... or could it be O(n)???
If we use recursive algorithms to sort (like mergesort/quicksort), the number of activation records placed on the stack depends on n, the number of elements being sorted. Would this make such an algorithm classify as non-in-place? Some resources classify quicksort as an in-pace algorithm and mergesort as non-in-place. I do not understand this.

It would be great if someone could please make the basis of calling an algo. "in-place" clear, by providing an example of an algorithm that sorts in-place, and one that does not.

Are the following in-place sorting algorithms?

-Bubblesort - I think yes (at least if implemented in imperative languages)

-Heapsort - I think yes

-Quicksort - I don't know

-Mergesort -I don't know

-Selection sort - I think yes

-Insertion sort - I think yes

Your responses will be highly appreciated!

Thanks very much!

Sincerely,
Sumithra
:confused:

[Manish Malik]

in-place sorting == a constant number of elements (may be 0 even) are ever stored outside the original array.

All those sorting algorithms can be implemented to work in-place, but that would raise the expected order O() of many; due to extra computations to manipulate available space.

This url, comparing various in-place algorithms, may help: http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html