Preliminaries

In-Place Sorting#

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.

Stable vs Unstable Sort#

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. [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. [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.