Understanding Sorting Algorithms

Introduction

Sorting is the process of arranging data in a specific order, typically in ascending or descending order. Sorting is one of the most fundamental concepts in computer science and is used in:

• Searching

• Databases

• Data organization

• File systems

• Analytics and reporting

Efficient sorting helps improve performance across many algorithms and applications.

In this chapter, you will learn the most popular sorting algorithms, how they work, and their time complexities.

Types of Sorting Algorithms

Sorting algorithms are generally classified into two categories:

1. Simple (Comparison-Based) Sorting Algorithms

• Bubble Sort

• Selection Sort

• Insertion Sort

These are easy to understand but not very efficient for large datasets.

2. Efficient (Divide and Conquer) Sorting Algorithms

• Merge Sort

• Quick Sort

• Heap Sort

• Counting Sort / Radix Sort (Non-comparison based)

These are used in real-world applications because they perform well with large datasets.

Bubble Sort

Bubble Sort compares adjacent elements and swaps them if they are out of order.

How It Works

Start: [5, 1, 4, 2]
Step 1: Compare 5 and 1 ? swap ? [1, 5, 4, 2]
Step 2: Compare 5 and 4 ? swap ? [1, 4, 5, 2]
Step 3: Compare 5 and 2 ? swap ? [1, 4, 2, 5]

C# Implementation

void BubbleSort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = 0; j < arr.Length - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
            }
        }
    }
}

Time Complexity

• Worst: O(n²)

• Best: O(n)

• Average: O(n²)

Selection Sort

Selection Sort finds the minimum element and places it at the beginning.

How It Works

[5, 3, 8, 1]
Find min ? 1 ? place at index 0 ? [1, 3, 8, 5]

C# Implementation

void SelectionSort(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

Time Complexity

• Worst: O(n²)

• Best: O(n²)

• Average: O(n²)

Insertion Sort

Insertion Sort places each element in its correct position in a sorted left-side portion.

How It Works

[5, 2, 4, 6]
Take 2 ? |5| ? insert before 5 ? [2, 5]
Take 4 ? insert between 2 and 5 ? [2, 4, 5]

C# Implementation

void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Time Complexity

• Worst: O(n²)

• Best: O(n)

• Average: O(n²)

Merge Sort

Merge Sort uses the divide-and-conquer method. It splits the array, sorts each part, and merges them.

How It Works

[8, 4, 2, 6]
Split ? [8,4] [2,6]
Sort ? [4,8] [2,6]
Merge ? [2,4,6,8]

C# Implementation

void MergeSort(int[] arr)
{
    if (arr.Length <= 1) return;

    int mid = arr.Length / 2;
    int[] left = arr[..mid];
    int[] right = arr[mid..];

    MergeSort(left);
    MergeSort(right);

    Merge(arr, left, right);
}

Time Complexity

• Worst: O(n log n)

• Best: O(n log n)

• Average: O(n log n)

Quick Sort

Quick Sort selects a pivot and partitions the array.

How It Works

[10, 7, 8, 9]
Pivot: 9
Left: [7,8]
Right: [10]

C# Implementation

void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

Time Complexity

• Worst: O(n²)

• Best: O(n log n)

• Average: O(n log n)

Heap Sort

Heap Sort uses a max heap to sort elements.

Time Complexity

• O(n log n)

It is efficient and uses constant space.

Counting Sort

Works when the range of input values is small.

Time Complexity

• O(n + k)

Summary

Sorting is an essential operation that affects performance across many systems.

Key takeaways:

• Bubble, Selection, Insertion ? simple but slow

• Merge, Quick, Heap ? efficient and widely used

• Counting & Radix Sort ? special-purpose, extremely fast