The Gateway to Computer Science Excellence
+1 vote
Is quick sort in-place algorithm?
in Algorithms by | 290 views
Yes,  quick sort is in place algorithm . . . As quick sort doesn't require new space it does the sorting in that array it self . . . Where as merge sort is not as it takes extra spaces for all the sub problems

1 Answer

+2 votes
Yes quicksort is an inplace algorithm as it does not require auxiliary array for sorting purpose like in the case of mergesort..
What about extra space for stack O(logn)?
Stack space is also taken by mergesort..That has to be taken for function calls ..So we are not considering that..We are only considering auxilliary space required for data..
So, If question is what is space complexity of Quick-sort? what should be answer O(1) or O(logn)
O(logn) in the worst case using tail call optimisation..
I think it will be depend upon question...

We have to write O(logn) in gneral case...

But with comparison to other algo's like merge habib said we will consider O(1)
Nope O(logn) else worst case complexity = O(n)..

It all depends on the definition of "in-place" algorithm.

If you define "in-place" as requiring a constant amount of memory, then quicksort is not "in-place" as it requires log(N) memory for the recursion.

If you define "in-place" as more human-friendly "does not move the data outside the input structure", then quicksort is again not "in-place".

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,489 answers
95,297 users