When we sort without using any additional space.
In computer science, an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.
For example: A sorting algorithm uses a temporary array of size 10000 (constant) elements. This algorithm is considered to be an IN-PLACE sorting algorithm.
Let's have an array: [3, 5, 2, 1, 5', 10] Both 5 and 5' are equal in value. So if the results after sorting are:
- [1, 2, 3, 5, 5', 10]
- This is known as a stable sort. Notice that 5 came before 5' in the original array and this order is maintained even after sorting.
- [1, 2, 3, 5', 5, 10]
- This is an unstable sort since the order of 5' and 5 is now different as compared to the original array.
- For example, in Insertion Sort, if we change the condition to
>=, even if the 2 elements are equal in value, their position will be changed and this becomes an unstable sort.