Introduction

The process of arranging the elements of an array in a particular order is called sorting. The order can be ascending or descending. How you want to sort the array depends on the problem you are solving. For example, If you have list of songs and you want to play them in a particular order, you can sort them by their names or by their duration. Different methods of comparison may lead to different results. At the most basic level, sorting algorithms are all about rearranging elements in a collection based on a common characteristic of those elements.

Definition

An ordering relation has two key properties: reflexivity and transitivity.

A relation $R$ is reflexive if $R(x, x)$ is true for all $x$. A relation $R$ is transitive if $R(x, y)$ and $R(y, z)$ imply $R(x, z)$. A relation $R$ is an ordering relation if it is reflexive and transitive.

In short,

1. Given two elements a and b, exactly one of the following must be true: $a < b$, $a = b$, or $a > b$ ( Law of Trichotomy )
2. If $a < b$ and $b < c$, then $a < c$ ( Law of Transitivity )

What is a Stable Sorting Algorithm?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

What is a In-Place Sorting Algorithm?

A sorting algorithm is said to be in-place if it uses only a constant amount of additional memory space. In-place sorting algorithms are often more efficient, since they do not require the creation of a new array to store the sorted elements.