What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.
The idea of an in-place algorithm isn't unique to sorting, but sorting is probably the most important case, or at least the most well-known. The idea is about space efficiency -
A sorting algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time. This was especially relevant to some devices (don't have enough space for ex. Embedded system like PDA, cellphone etc.)
The idea is to produce an output in the same memory space that contains the input by successively transforming that data (mainly by replacing) until the output is produced. This avoids the need to use twice the storage - one area for the input and an equal-sized area for the output.
A/c to Wikipedia page on in-place algorithms currently claims that an in-place algorithm can only use a constant amount - O(1) - of extra space.
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.
However, all algorithms require some additional storage for working variables.
Some In-place sorting algorithms :
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort (modification in implementation)