A Sorting Algorithm is used to rearrange a given list of elements according to a comparison
operator on the elements. The output should have the exact same elements that the input (no
element added or removed) with the elements reordered.
Characteristics of sorting algorithms
● Time Complexity: it’s a measure of how long it takes to run an algorithm, is used to
categorize sorting algorithms. There can be different values for the best-case,
average case and worst case scenario.
● Space Complexity: it’s the amount of memory required to execute the algorithm.
● Stability: a sorting algorithm is stable if the relative order of equal elements is
preserved after sorting. This is crutial in certain applications where the original order
of equal elements must be maintained.
● In-Place Sorting: an in-place sorting algorithm is one that does not require
additional memory to sort the data. This is something to consider when the available
memory is limited or when the data cannot be moved.
● Adaptivity: a sorting algorithm is adaptive when it takes advantage of pre-existing
order in the data to improve performance.
● Serial or parallel: sorting algorithms can be designed to work on a single computer
processor (serial) or on multiple processors simultaneously (parallel).
● Online: a sorting algorithm that can continuously sort a list as new elements are
added to it. It can handle a constant stream of incoming data.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not efficient for large data sets as its
average and worst-case time complexity are quite high.
● Sorts the array using multiple passes. After the first pass, the maximum goes to the
end (its correct position). Same way, after the second pass, the second largest goes to
second last position and so on.
● In every pass, process only those that have already not moved to the correct position.
After k passes, the largest k must have been moved to the last k positions.
● In a pass, we consider remaining elements and compare all adjacent and swap if a
larger element is before a smaller element. If we keep doing this, we get the largest
(among the remaining elements) at its correct position.
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts by repeatedly selecting the
smallest (or largest) element from the unsorted portion and swapping it with the first unsorted
element.
1. Find the smallest element and swap it with the first element. This way we get the
smallest element at its correct position.
2. Then find the smallest among remaining elements (or second smallest) and swap it
with the second element.
3. We keep doing this until we get all elements moved to the correct position.
Advantages of Selection Sort
● Easy to understand and implement, making it ideal for teaching basic sorting
concepts.
● Requires only a constant O(1) extra memory space.
● It requires less number of swaps (or memory writes) compared to many other
standard algorithms. Only cycle sort beats it in terms of memory writes. Therefore it
can be a simple algorithm choice when memory writes are costly.
Disadvantages of the Selection Sort
● Selection sort has a time complexity of O(n^2) which makes it slower compared to
algorithms like Quick Sort or Merge Sort.
● Does not maintain the relative order of equal elements which means it is not stable.
Applications of Selection Sort
● Perfect for teaching fundamental sorting mechanisms and algorithm design.
● Suitable for small lists where the overhead of more complex algorithms isn't justified
and memory writing is costly as it requires less memory writes compared to other
standard sorting algorithms.
● The Heap Sort algorithm is based on Selection Sort.
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an
unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards
in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then,
you pick a card from the unsorted group and put it in the right place in the sorted group.
● Start with the second element as the first element is assumed to be sorted.
● Compare the second element with the first if the second is smaller then swap them.
● Move to the third element, compare it with the first two, and put it in its correct
position
● Repeat until the entire array is sorted.
Advantages and Disadvantages of Insertion Sort
Advantages
● Simple and easy to implement.
● Stable sorting algorithm.
● Efficient for small lists and nearly sorted lists.
● Space-efficient as it is an in-place algorithm.
● Adoptive. the number of inversions is directly proportional to the number of swaps.
For example, no swapping happens for a sorted array and it takes O(n) time only.
Disadvantages
● Inefficient for large lists.
● Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most
cases.
Applications of Insertion Sort
Insertion sort is commonly used in situations where:
● The list is small or nearly sorted.
● Simplicity and stability are important.
● Used as a subroutine in Bucket Sort
● Can be useful when array is already almost sorted (very few inversions)
Merge Sort
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the
Divide and Conquer approach. It works by recursively dividing the input array into two halves,
recursively sorting the two halves and finally merging them back together to obtain the sorted
array.
Here's a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no longer be
divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The process
continues until all elements from both subarrays have been merged.
Let's sort the array or list [38, 27, 43, 10] using Merge Sort
Let's look at the working of above example:
Divide:
● [38, 27, 43, 10] is divided into [38, 27] and [43, 10] .
● [38, 27] is divided into [38] and [27] .
● [43, 10] is divided into [43] and [10] .
Conquer:
● [38] is already sorted.
● [27] is already sorted.
● [43] is already sorted.
● [10] is already sorted.
Merge:
● Merge [38] and [27] to get [27, 38] .
● Merge [43] and [10] to get [10,43] .
● Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]
Therefore, the sorted list is [10, 27, 38, 43]
Advantages and Disadvantages of Merge Sort
Advantages
● Stability : Merge sort is a stable sorting algorithm, which means it maintains the
relative order of equal elements in the input array.
● Guaranteed worst-case performance: Merge sort has a worst-case time complexity
of O(N logN) , which means it performs well even on large datasets.
● Simple to implement: The divide-and-conquer approach is straightforward.
● Naturally Parallel : We independently merge subarrays that make them suitable for
parallel processing.
Disadvantages
● Space complexity: Merge sort requires additional memory to store the merged
sub-arrays during the sorting process.
● Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires
additional memory to store the sorted data. This can be a disadvantage in applications
where memory usage is a concern.
● Merge Sort is slower than QuickSort in general as QuickSort is more cache
friendly because it works in-place.
Applications of Merge Sort:
● Sorting large datasets
● External sorting (when the dataset is too large to fit in memory)
● Used to solve problems like Inversion counting, Count Smaller on Right & Surpasser
Count
● It is a preferred algorithm for sorting Linked lists.
● It can be easily parallelized as we can independently sort subarrays and then merge.