Question

Which Sorting algorithm are in place algorithm and which are not? Is it advantageous to design in place sorting algorithm? How this in place term is related to the time complexity and space complexity of the program?

Answer 1

In-place algorithms are algorithms that use only a constant amount extra space in addition to the input.Usually overwrites the input space.

We generally consider algorithms in Language L,which require additional space of O(logn) where n is the number of elements in your input array.

These algorithms may take longer execution time since more instructions and arithmetic takes longer time than just assigning value to a different array.

Sorting Algorithms that are in-place algorithm:  

bubble sort, comb sort, selection sort, insertion sort, heapsort, and Shell sort.

Out of place Sorting algorithms:

Quicksort,Merge Sort

These designs are advantageous wrt space constraints not with time constraints as some devices don’t have enough space –Embedded system like PDA,cellphone .

Strict definition of in-place algorithm considers algorithms with O(1) space complexity,the class Dspace(1) but we generally consider algorithm with space complexity of O(logn) as in space algorithm.