# Algorithm refresher. Why is heapsort an insort algorithm?

I can not see why the heapsort is considered an inplace sorting algorithm.

I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.

So may be I am misunderstanding the definition of inplace here?

But insertion sort for example it is obvious that it is inplace algorith, i.e. no extra memory needed for the elements.

So why is it considered inplace?

I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.

No. The array is transformed to conform to the heap constraint without using more than O(1) extra memory. (In fact all you need is extra memory sufficient to hold one element of the array, for swap purposes, plus a boolean or two and a loop variable or two).

Ok, on a technicality it may be that heapsort is usually explained as using a separate heap, but it's perfectly possible to implement it in-place.

• The only place I'd expect to see "heapsort" with a separate heap (in code) is in a functional language like Haskell, for the same reason that the usual functional "Quicksort" isn't in-place too - functional programmers like their lists a lot, and an in-place sort is stateful - it changes the state of the array/whatever containing the data. Scare-quotes because I don't really accept that an out-of-place quicksort is a quicksort at all, or that an out-of-place heapsort is a heapsort at all - at least not without clearly saying that it's not in-place.
– user8709
Oct 30, 2011 at 5:01
• @Steve314, I think I've seen some teaching material which says something to the effect of "put it in a heap and then pull the elements out one at a time and put them in an array". But having just checked CLR I can report that they do show an in-place version. Oct 30, 2011 at 7:46
• @PeterTaylor:Yes, the book I was reviewing (Skiena) presented heapsort by building an extra heap. Oct 30, 2011 at 8:15

You may be missing the fundamental understanding that an array can be used to specify the layout of a tree.

Suppose you have a binary tree, and an interior node is at index i of the array. Then the array index of the parent and children of that node can be found by:

``````Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1
``````

See:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Since the heap can be kept and organised entirely in an array, then heapsort can run in-place by moving elements around inside the input array. Indeed, the heap is built and manipulated using the original input array.

• :I know about this.The problems seems to be that the book I am reading presented heapsort using a separate heap.I did not understand or think that this presentation was to make it easier to understand the algorithm (perhaps? not sure why it was presented like that) Oct 30, 2011 at 8:13
• I would highly recommend you purchase the book "Introduction to Algorithms" by Cormen, et al. It clearly answers all algorithm-related questions. If you are serious about a career as a computer scientist or software engineer, then you need to have this book. Oct 30, 2011 at 17:55

If, as you say, one really needed an extra structure to build the heap then heapsort would indeed NOT be an inplace sorting algorithm.

However, this is not the case. You can build the heap on the very same array you wanna sort, and after that you apply the heapsort algorithm, so it sorts inplace.

• Basically, there's a "heapify" algorithm which is used to re-order data in an array so that it complies with the rules of a heap in IIRC O(n) time. See the pseudocode on programmers.stackexchange.com/questions/116904/…. After then, it's mostly a matter of doing repeated heap root-extracts and keeping track of how much of the array is still "heap" and how much is sorted end-result.
– user8709
Oct 30, 2011 at 5:10

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

Wikipedia - In-place algorithm

• So why mergesort is considered an not-in-place algorithm then? Oct 29, 2011 at 21:35
• This is not a useful reply. It has nothing to do with heapsort and does not answer the question. Oct 30, 2011 at 4:51
• Of course it has something to do with heapsort. Heapsort is an in-place sort algorithm, as should be clear from the definition. In fact, it was linked from the heapsort page. Oct 31, 2011 at 8:32

It is considered in place because it's space requirements are negligible (constant or none at all if you're using bitwise operations to swap items). MergeSort, for example, is not in place because the input set is not modified in each iteration of the search example.

The best way to illustrate the differences between in-place algorithms and out-of-place algorithms is probably to look at the following C/C++ string reversal code that does it in place (from K&R):

``````void reverse(char s[])
{
int c, i, j;

for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
``````

If you were, for example, reading the input string from the end and placing the characters in another buffer, it would be an out-of place string reversal algorithm.

• Mergesort is damned annoying - it's easy to wrongly convince yourself that you have an in-place strategy. Usually, it only works for small arrays. However, I think I downloaded a paper once where someone did work out an in-place variant of the merge-sort algorithm. I'll see if I can find it again.
– user8709
Oct 30, 2011 at 5:25