In this series of Trivial Sorting Algorithms tutorials, we will go through some simple sorting algorithms like Bubble Sort, Insertion Sort and Shell Sort to see how they work. We will also try to find out why they are ineffective for large data samples and how we may improve upon them. But before going any further, it would be instructive if we took a sample scenario/problem that we might encounter and presented our algorithms as solutions to that problem.

(Image credits)

So, let us define our problem statement and constraints first.

Problem Statement:

Suppose we have microcontroller or embedded system in which we need to implement a sorting mechanism. It takes an array and its size as input and sorts the given array.

Constraints:

1. Code footprint should not be more than some kilobytes.
2. Stack size is very limited, so do not use any form of recursion.
3. Memory is limited, so try to minimize the space complexity.

Sample Data Property:

In the practical scenario, the size of data is not going to be more than 50 elements and will also be having minimum inversion or, simply put, the input array would be partially sorted.

Solution:

For the sake of simplicity, we will construct our algorithms on an integer array a[] containing N elements.

Upon analysing the constraints and the data property, it suffices to say that complex and elegant sorting algorithms such as Merge sort, Quick Sort and Heap Sort will not solve our problem, as these have complex structures and thus, have a large code footprint. Also, in merge sort, there is O(N) extra space requirement, and recursion is an important part of all these solutions.

So these constraints leave us to use the trivial sorting mechanisms which have minimal code footprint but higher time complexity. We will analyse the methods involved and try to find which one is better and why.

The following algorithms will be analysed in the same order:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Shell Sort