# Preliminaries

## #

In-Place SortingWhen 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.

## #

Stable vs Unstable SortLet'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.