Sorting means arranging a given array or list of elements based on a comparison operator. This operator helps determine the new order of the elements in the data structure. For example, you may need to sort the array in descending or ascending order, or perhaps sort all the 0's first and then all the 1's.

But the main question arises: why are they important? I mean, yes, reading them becomes easier, but we don't read data manually; the machine does. So why does it matter if all the 0's are first or in the middle?

In one word—Time Complexity. Sorry, that's two words, but the point is to improve time complexity. In previous lectures, we learned the importance of time complexity, so for every algorithm or piece of code, the next step is always to improve its time complexity, if possible.

• When you have millions of data entries to print, you might want to organize them in a certain order so they're readable to humans.

• Once the data is sorted, we can find the k-th smallest and k-th largest item in O(1) time, and many more functions can be performed very efficiently.

• It also leads to better algorithms like binary search, which literally simplifies the entire searching process.

And many more….

So let's start with the basics—

Let's understand the different types of sorting—

Types of Sorting

In-place Sorting:

An in-place sorting algorithm modifies the input array directly without requiring additional space for the output. It uses only a constant amount of extra memory.

For example: If I sort an array, let's say [1, 3, 2], without creating any other array, it is called in-place sorting.

Internal Sorting:

Internal sorting refers to sorting algorithms that process data entirely within the main memory (RAM). All the data to be sorted must fit into the available memory.

For example, if a sorting algorithm sorts an array using only the main memory (RAM) without using external storage like a disk or cloud, it is called internal sorting.

Example: Sorting an array [5, 2, 8, 1] using QuickSort within the RAM is an internal sorting process.

External Sorting:

External sorting is used when the data is too large to fit into the main memory. Instead, it relies on external storage, like disks, and processes the data in chunks.

For example, if a sorting algorithm uses external storage, like a disk, to sort an array because the data is too large for the main memory (RAM), it is called external sorting.

Example: Sorting a large dataset stored in a file using Merge Sort with disk storage is an external sorting process.

Stable Sorting:

A stable sorting algorithm maintains the relative order of elements with equal keys in the sorted output as they were in the original input.

For example: If a sorting algorithm maintains the relative order of equal elements after sorting, it is called stable sorting.

Example: Sorting an array [(3, A), (1, B), (3, C)] using Merge Sort will keep (3, A) before (3, C), ensuring stability.

Hybrid Sorting:

A hybrid sorting algorithm combines two or more standard sorting algorithms to leverage their strengths.

For example: If a sorting algorithm combines two or more sorting techniques to improve performance, it is called hybrid sorting.

Example: Timsort combines Merge Sort and Insertion Sort to efficiently sort an array [7, 3, 5, 1, 9, 2].

So, these were the different types of sorting. Now, let's understand the different types of sorting techniques. Pretty confusing, right? The difference between types of sorting and types of sorting techniques, but here is the difference.

• Types of Sorting refer to the classification based on properties like stability, memory usage, and external dependencies. Examples include in-place sorting, stable sorting, internal sorting, external sorting, and hybrid sorting.

• Types of Sorting Techniques refer to the actual methods used to sort data, such as Bubble Sort, QuickSort, Merge Sort, Insertion Sort, Heap Sort, and Radix Sort. These techniques follow different algorithms to arrange data in a specific order.

Types of Sorting Techniques

There are various sorting algorithms used in data structures, which can be broadly classified into two types:

1. Comparison-Based Sorting:

In comparison-based sorting, elements are compared with each other to determine their order. The sorting process relies on operations like <, >, == to decide the arrangement.

For Example:

Imagine arranging students in a class based on their heights. You compare two students at a time and swap them if needed until the entire class is sorted from shortest to tallest.

Common Algorithms:

• Bubble Sort – Compares adjacent elements and swaps them if needed.

• Merge Sort – Divides the array, sorts each part, and merges them.

• QuickSort – Picks a pivot and arranges elements based on comparisons.

• Heap Sort – Uses a heap data structure for sorting.

2. Non-Comparison-Based Sorting:

In non-comparison-based sorting, elements are sorted without direct comparisons. These algorithms use techniques like counting, hashing, or digit-based sorting to arrange elements efficiently.

For Example:

Consider sorting exam papers based on roll numbers. Instead of comparing roll numbers one by one, you directly place each paper in its correct slot using the roll number as an index, like a Counting Sort.

Common Algorithms:

• Counting Sort – Counts occurrences of each number and places them accordingly.

• Radix Sort – Sorts numbers digit by digit, like sorting phone numbers.

• Bucket Sort – Groups elements into buckets and sorts them separately.

Key Difference:

• Comparison-based sorting works on any type of data and is widely used.

• Non-comparison-based sorting is faster but works best when the range of numbers is limited.

So now we have learned what sorting is, why it's important, and the different types and techniques. Let's dive into the real deal: different sorting algorithms.

There are many types of sorting algorithms, but we are going to learn these eight:

• Bubble Sort

• Insertion Sort

• Selection Sort

• Quick Sort

• Heap Sort

• Merge Sort

• Counting Sort

• Radix Sort

So lets begin——

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms to understand and implement

What is Bubble Sort?

Bubble Sort is a comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list (beginning of the array) with each iteration.

How Bubble Sort Works

Let’s break down the steps of Bubble Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: First Pass

• Compare the first two elements (5 and 3). Since 5 > 3, swap them.

• Array: [3, 5, 8, 4, 6]

• Compare 5 and 8. No swap needed.

• Compare 8 and 4. Swap them.

• Array: [3, 5, 4, 8, 6]

• Compare 8 and 6. Swap them.

• Array: [3, 5, 4, 6, 8]

After the first pass, the largest element (8) is in its correct position at the end of the array.

Step 2: Second Pass

• Compare 3 and 5. No swap needed.

• Compare 5 and 4. Swap them.

• Array: [3, 4, 5, 6, 8]

• Compare 5 and 6. No swap needed.

After the second pass, the second largest element (6) is in its correct position.

Step 3: Third Pass

• Compare 3 and 4. No swap needed.

• Compare 4 and 5. No swap needed.

After the third pass, the third largest element (5) is in its correct position.

Step 4: Fourth Pass

• Compare 3 and 4. No swap needed.

After the fourth pass, the array is fully sorted.

Visual Representation of Bubble Sort

Initial Array: [5, 3, 8, 4, 6]
After First Pass: [3, 5, 4, 6, 8]
After Second Pass: [3, 4, 5, 6, 8]
After Third Pass: [3, 4, 5, 6, 8]
After Fourth Pass: [3, 4, 5, 6, 8]

Implementation of Bubble Sort

public class BubbleSort {

    /**
     * Sorts an array using the Bubble Sort algorithm.
     *
     * @param arr The array to be sorted.
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length; // Get the length of the array

        // Traverse through all elements in the array
        for (int i = 0; i < n - 1; i++) {
            // Flag to detect if any swapping happened
            boolean swapped = false;

            // Last i elements are already in place, so no need to check them
            for (int j = 0; j < n - i - 1; j++) {
                // Compare adjacent elements
                if (arr[j] > arr[j + 1]) {
                    // Swap if the element found is greater than the next element
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true; // Set the swapped flag to true
                }
            }

            // If no elements were swapped, the array is already sorted
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Bubble Sort
        bubbleSort(unsortedArray);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. bubbleSort Method:

   • This method implements the Bubble Sort algorithm.

   • It uses two nested loops:

     • The outer loop (for i) runs n-1 times, where n is the length of the array.

     • The inner loop (for j) compares adjacent elements and swaps them if they are in the wrong order.

   • The swapped flag is used to optimize the algorithm. If no swaps occur during a pass, the array is already sorted, and the algorithm terminates early.

2. printArray Method:

   • This method prints the elements of the array in a readable format.

3. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the bubbleSort method, and then prints the sorted array.

Time Complexity

• Worst-case and Average-case Time Complexity: O(n²)

  • This occurs when the array is in reverse order, and the algorithm requires maximum comparisons and swaps.

• Best-case Time Complexity: O(n)

  • This occurs when the array is already sorted, and the algorithm terminates after the first pass.

When to Use Bubble Sort?

Bubble Sort is suitable for:

• Small datasets.

• Educational purposes to understand sorting algorithms.

• Situations where simplicity is more important than efficiency.

For larger datasets, more efficient algorithms like Quick Sort or Merge Sort are recommended.

Insertion Sort

Insertion Sort is another simple sorting algorithm that builds the final sorted array one element at a time. It is much more efficient than Bubble Sort for small datasets and is often used in practice for small or nearly sorted datasets.

What is Insertion Sort?

Insertion Sort works by dividing the array into a sorted and an unsorted part. It repeatedly takes the first element from the unsorted part and inserts it into the correct position in the sorted part. This process continues until the entire array is sorted.

How Insertion Sort Works

Let’s break down the steps of Insertion Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: Initial State

• The first element (5) is considered sorted.

• Sorted part: [5]

• Unsorted part: [3, 8, 4, 6]

Step 2: Insert 3

• Take the first element from the unsorted part (3) and insert it into the sorted part.

• Compare 3 with 5. Since 3 < 5, insert 3 before 5.

• Sorted part: [3, 5]

• Unsorted part: [8, 4, 6]

Step 3: Insert 8

• Take the first element from the unsorted part (8) and insert it into the sorted part.

• Compare 8 with 5. Since 8 > 5, it remains in place.

• Sorted part: [3, 5, 8]

• Unsorted part: [4, 6]

Step 4: Insert 4

• Take the first element from the unsorted part (4) and insert it into the sorted part.

• Compare 4 with 8. Since 4 < 8, move 8 to the right.

• Compare 4 with 5. Since 4 < 5, move 5 to the right.

• Compare 4 with 3. Since 4 > 3, insert 4 after 3.

• Sorted part: [3, 4, 5, 8]

• Unsorted part: [6]

Step 5: Insert 6

• Take the first element from the unsorted part (6) and insert it into the sorted part.

• Compare 6 with 8. Since 6 < 8, move 8 to the right.

• Compare 6 with 5. Since 6 > 5, insert 6 after 5.

• Sorted part: [3, 4, 5, 6, 8]

• Unsorted part: []

Visual Representation of Insertion Sort

Initial Array: [5, 3, 8, 4, 6]
After Step 1: [5 | 3, 8, 4, 6]
After Step 2: [3, 5 | 8, 4, 6]
After Step 3: [3, 5, 8 | 4, 6]
After Step 4: [3, 4, 5, 8 | 6]
After Step 5: [3, 4, 5, 6, 8]

Implementation of Insertion Sort

public class InsertionSort {

    /**
     * Sorts an array using the Insertion Sort algorithm.
     *
     * @param arr The array to be sorted.
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length; // Get the length of the array

        // Traverse through the array starting from the second element
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // The element to be inserted into the sorted part
            int j = i - 1; // Start comparing with the last element of the sorted part

            // Move elements of the sorted part that are greater than the key
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // Shift the element to the right
                j--;
            }

            // Insert the key into its correct position
            arr[j + 1] = key;
        }
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Insertion Sort
        insertionSort(unsortedArray);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. insertionSort Method:

   • This method implements the Insertion Sort algorithm.

   • It uses a loop to traverse the array starting from the second element (i = 1).

   • The key is the current element to be inserted into the sorted part.

   • The inner while loop shifts elements greater than the key to the right and finds the correct position for the key.

2. printArray Method:

   • This method prints the elements of the array in a readable format.

3. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the insertionSort method, and then prints the sorted array.

Time Complexity

• Worst-case and Average-case Time Complexity: O(n²)

  • This occurs when the array is in reverse order, and the algorithm requires maximum comparisons and shifts.

• Best-case Time Complexity: O(n)

  • This occurs when the array is already sorted, and the algorithm only needs to traverse the array once.

When to Use Insertion Sort?

Insertion Sort is suitable for:

• Small datasets.

• Nearly sorted datasets.

• Situations where simplicity and low overhead are important.

For larger datasets, more efficient algorithms like Quick Sort or Merge Sort are recommended.

Selection Sort

What is Selection Sort?

Selection Sort divides the array into a sorted and an unsorted part. It repeatedly finds the smallest element in the unsorted part and swaps it with the first unsorted element. This way, the sorted part grows, and the unsorted part shrinks until the entire array is sorted.

How Selection Sort Works

Let’s break down the steps of Selection Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: Initial State

• The entire array is unsorted.

• Find the smallest element in the unsorted part (3) and swap it with the first element (5).

• Array: [3, 5, 8, 4, 6]

• Sorted part: [3]

• Unsorted part: [5, 8, 4, 6]

Step 2: Find the Next Smallest Element

• Find the smallest element in the unsorted part (4) and swap it with the first unsorted element (5).

• Array: [3, 4, 8, 5, 6]

• Sorted part: [3, 4]

• Unsorted part: [8, 5, 6]

Step 3: Find the Next Smallest Element

• Find the smallest element in the unsorted part (5) and swap it with the first unsorted element (8).

• Array: [3, 4, 5, 8, 6]

• Sorted part: [3, 4, 5]

• Unsorted part: [8, 6]

Step 4: Find the Next Smallest Element

• Find the smallest element in the unsorted part (6) and swap it with the first unsorted element (8).

• Array: [3, 4, 5, 6, 8]

• Sorted part: [3, 4, 5, 6]

• Unsorted part: [8]

Step 5: Final State

• The last element (8) is already in its correct position.

• Array: [3, 4, 5, 6, 8]

• Sorted part: [3, 4, 5, 6, 8]

• Unsorted part: []

Visual Representation of Selection Sort

Initial Array: [5, 3, 8, 4, 6]
After Step 1: [3 | 5, 8, 4, 6]
After Step 2: [3, 4 | 8, 5, 6]
After Step 3: [3, 4, 5 | 8, 6]
After Step 4: [3, 4, 5, 6 | 8]
After Step 5: [3, 4, 5, 6, 8]

Implementation of Selection Sort

public class SelectionSort {

    /**
     * Sorts an array using the Selection Sort algorithm.
     *
     * @param arr The array to be sorted.
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length; // Get the length of the array

        // Traverse through the array
        for (int i = 0; i < n - 1; i++) {
            // Find the index of the smallest element in the unsorted part
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // Update the index of the smallest element
                }
            }

            // Swap the smallest element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Selection Sort
        selectionSort(unsortedArray);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. selectionSort Method:

   • This method implements the Selection Sort algorithm.

   • It uses two nested loops:

     • The outer loop (for i) traverses the array and selects the position for the smallest element.

     • The inner loop (for j) finds the smallest element in the unsorted part of the array.

   • After finding the smallest element, it swaps it with the first unsorted element.

2. printArray Method:

   • This method prints the elements of the array in a readable format.

3. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the selectionSort method, and then prints the sorted array.

Time Complexity

• Worst-case, Average-case, and Best-case Time Complexity: O(n²)

When to Use Selection Sort?

Selection Sort is suitable for:

• Small datasets.

• Situations where memory usage is a concern (it uses minimal extra memory).

• Educational purposes to understand sorting algorithms.

For larger datasets, more efficient algorithms like Quick Sort or Merge Sort are recommended.

Quick Sort

Quick Sort is a highly efficient sorting algorithm that uses a divide-and-conquer approach to sort elements. It works by selecting a "pivot" element and partitioning the array into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot. This process is repeated recursively until the entire array is sorted.

What is Quick Sort?

Quick Sort is a comparison-based algorithm that works as follows:

1. Choose a Pivot: Select an element from the array as the pivot.

2. Partitioning: Rearrange the array so that all elements less than the pivot are on its left, and all elements greater than the pivot are on its right.

3. Recursively Sort: Apply the same process to the left and right sub-arrays.

How Quick Sort Works

Let’s break down the steps of Quick Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: Choose a Pivot

• Let’s choose the last element (6) as the pivot.

Step 2: Partitioning

• Rearrange the array so that elements less than 6 are on the left, and elements greater than 6 are on the right.

• After partitioning:

  • Left sub-array: [5, 3, 4]

  • Pivot: [6]

  • Right sub-array: [8]

Step 3: Recursively Sort Left Sub-array

• Choose the last element (4) as the pivot.

• Partition the left sub-array:

  • Left sub-array: [3]

  • Pivot: [4]

  • Right sub-array: [5]

• Since the sub-arrays [3] and [5] have only one element, they are already sorted.

Step 4: Recursively Sort Right Sub-array

• The right sub-array [8] has only one element, so it is already sorted.

Step 5: Combine Results

• Combine the sorted left sub-array, pivot, and sorted right sub-array:

  • [3, 4, 5, 6, 8]

Visual Representation of Quick Sort

Initial Array: [5, 3, 8, 4, 6]
After Partitioning: [5, 3, 4 | 6 | 8]
After Sorting Left Sub-array: [3, 4, 5 | 6 | 8] 
Final Sorted Array: [3, 4, 5, 6, 8]

Implementation of Quick Sort

public class QuickSort {

    /**
     * Sorts an array using the Quick Sort algorithm.
     *
     * @param arr The array to be sorted.
     * @param low The starting index of the array.
     * @param high The ending index of the array.
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(arr, low, high);

            // Recursively sort the left and right sub-arrays
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    /**
     * Partitions the array around the pivot element.
     *
     * @param arr The array to be partitioned.
     * @param low The starting index of the array.
     * @param high The ending index of the array.
     * @return The index of the pivot element.
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Choose the last element as the pivot
        int i = low - 1; // Index of the smaller element

        // Traverse through the array
        for (int j = low; j < high; j++) {
            // If the current element is smaller than or equal to the pivot
            if (arr[j] <= pivot) {
                i++; // Increment the index of the smaller element
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap the pivot element with the element at index i+1
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // Return the pivot index
        return i + 1;
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Quick Sort
        quickSort(unsortedArray, 0, unsortedArray.length - 1);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. quickSort Method:

   • This method implements the Quick Sort algorithm.

   • It recursively sorts the left and right sub-arrays around the pivot.

2. partition Method:

   • This method partitions the array around the pivot.

   • It selects the last element as the pivot and rearranges the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

3. printArray Method:

   • This method prints the elements of the array in a readable format.

4. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the quickSort method, and then prints the sorted array.

Time Complexity

• Worst-case Time Complexity: O(n²)

  • This occurs when the pivot is always the smallest or largest element (e.g., when the array is already sorted or reverse-sorted).

• Average-case Time Complexity: O(n log n)

  • This is the typical performance for randomly ordered arrays.

• Best-case Time Complexity: O(n log n)

  • This occurs when the pivot always divides the array into two nearly equal parts.

When to Use Quick Sort?

Quick Sort is suitable for:

• Large datasets.

• Situations where average-case performance is more important than worst-case performance.

• In-place sorting (requires minimal extra memory).

For small datasets or when worst-case performance is critical, consider using Insertion Sort or Merge Sort.

Merge Sort

Merge Sort is a highly efficient, stable, and comparison-based sorting algorithm that uses a divide-and-conquer approach. It works by dividing the array into two halves, sorting each half recursively, and then merging the two sorted halves.

What is Merge Sort?

Merge Sort works as follows:

1. Divide: Split the array into two halves.

2. Conquer: Recursively sort each half.

3. Combine: Merge the two sorted halves into a single sorted array.

How Merge Sort Works

Let’s break down the steps of Merge Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: Divide the Array

• Split the array into two halves:

  • Left half: [5, 3]

  • Right half: [8, 4, 6]

Step 2: Recursively Sort the Left Half

• Split [5, 3] into [5] and [3].

• Merge [5] and [3] into [3, 5].

Step 3: Recursively Sort the Right Half

• Split [8, 4, 6] into [8] and [4, 6].

• Split [4, 6] into [4] and [6].

• Merge [4] and [6] into [4, 6].

• Merge [8] and [4, 6] into [4, 6, 8].

Step 4: Merge the Two Sorted Halves

• Merge the left half [3, 5] and the right half [4, 6, 8] into the final sorted array:

  • Compare 3 and 4 → Add 3.

  • Compare 5 and 4 → Add 4.

  • Compare 5 and 6 → Add 5.

  • Compare 6 and 8 → Add 6.

  • Add the remaining 8.

• Final sorted array: [3, 4, 5, 6, 8]

Visual Representation of Merge Sort

Initial Array: [5, 3, 8, 4, 6]
After Dividing: [5, 3] and [8, 4, 6]
After Sorting Left Half: [3, 5]
After Sorting Right Half: [4, 6, 8]
After Merging: [3, 4, 5, 6, 8]

Implementation of Merge Sort

public class MergeSort {

    /**
     * Sorts an array using the Merge Sort algorithm.
     *
     * @param arr The array to be sorted.
     * @param left The starting index of the array.
     * @param right The ending index of the array.
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point to divide the array into two halves
            int mid = left + (right - left) / 2;

            // Recursively sort the left and right halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    /**
     * Merges two sorted sub-arrays into a single sorted array.
     *
     * @param arr The array containing the sub-arrays to be merged.
     * @param left The starting index of the first sub-array.
     * @param mid The ending index of the first sub-array.
     * @param right The ending index of the second sub-array.
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        // Sizes of the two sub-arrays
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays to hold the two halves
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to the temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }

        // Merge the two temporary arrays back into the original array
        int i = 0, j = 0; // Initial indices of the two sub-arrays
        int k = left; // Initial index of the merged array

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArray (if any)
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArray (if any)
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Merge Sort
        mergeSort(unsortedArray, 0, unsortedArray.length - 1);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. mergeSort Method:

   • This method implements the Merge Sort algorithm.

   • It recursively divides the array into two halves, sorts them, and then merges them.

2. merge Method:

   • This method merges two sorted sub-arrays into a single sorted array.

   • It uses temporary arrays to hold the two halves and then merges them back into the original array.

3. printArray Method:

   • This method prints the elements of the array in a readable format.

4. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the mergeSort method, and then prints the sorted array.

Time Complexity

• Worst-case, Average-case, and Best-case Time Complexity: O(n log n)

Space Complexity

• Space Complexity: O(n)

When to Use Merge Sort?

Merge Sort is suitable for:

• Large datasets.

• Situations where stability is important (equal elements retain their relative order).

• External sorting (e.g., sorting data that doesn’t fit in memory).

For small datasets or when memory usage is a concern, consider using Insertion Sort or Quick Sort.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by building a max-heap (or min-heap) from the input array and repeatedly extracting the largest (or smallest) element from the heap and placing it at the end of the array.

What is Heap Sort?

Heap Sort works as follows:

1. Build a Max-Heap: Convert the input array into a max-heap, where the largest element is at the root.

2. Extract Elements: Repeatedly extract the largest element from the heap and place it at the end of the array.

3. Heapify: Restore the heap property after each extraction.

How Heap Sort Works

Let’s break down the steps of Heap Sort with an example. Consider the following unsorted array:

[5, 3, 8, 4, 6]

Step 1: Build a Max-Heap

• Convert the array into a max-heap:

  • Start from the last non-leaf node and heapify each node.

  • After building the max-heap, the array becomes: [8, 6, 5, 4, 3]

Step 2: Extract Elements

• Swap the root (largest element) with the last element of the heap.

• Array after swap: [3, 6, 5, 4, 8]

• Reduce the heap size by 1 (ignore the last element).

Step 3: Heapify

• Restore the max-heap property for the remaining elements.

• After heapify: [6, 4, 5, 3]

Step 4: Repeat Extraction and Heapify

• Swap the root (6) with the last element (3).

• Array after swap: [3, 4, 5, 6, 8]

• Reduce the heap size by 1.

• Heapify the remaining elements: [5, 4, 3]

Step 5: Continue Until the Heap is Empty

• Swap the root (5) with the last element (3).

• Array after swap: [3, 4, 5, 6, 8]

• Reduce the heap size by 1.

• Heapify the remaining elements: [4, 3]

Step 6: Final Extraction

• Swap the root (4) with the last element (3).

• Array after swap: [3, 4, 5, 6, 8]

• Reduce the heap size by 1.

• Heapify the remaining elements: [3]

Step 7: Final Sorted Array

• The array is now fully sorted: [3, 4, 5, 6, 8]

Visual Representation of Heap Sort

Initial Array: [5, 3, 8, 4, 6]
After Building Max-Heap: [8, 6, 5, 4, 3]
After First Extraction and Heapify: [6, 4, 5, 3, 8]
After Second Extraction and Heapify: [5, 4, 3, 6, 8]
After Third Extraction and Heapify: [4, 3, 5, 6, 8]
After Fourth Extraction and Heapify: [3, 4, 5, 6, 8]
Final Sorted Array: [3, 4, 5, 6, 8]

Implementation of Heap Sort

public class HeapSort {

    /**
     * Sorts an array using the Heap Sort algorithm.
     *
     * @param arr The array to be sorted.
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Build the max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements from the heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Swap the root (largest element) with the last element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify the reduced heap
            heapify(arr, i, 0);
        }
    }

    /**
     * Heapifies a subtree rooted at the given index.
     *
     * @param arr The array representing the heap.
     * @param n The size of the heap.
     * @param i The index of the root of the subtree.
     */
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize the largest element as the root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child

        // If the left child is larger than the root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If the right child is larger than the largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If the largest is not the root
        if (largest != i) {
            // Swap the root with the largest element
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            // Recursively heapify the affected subtree
            heapify(arr, n, largest);
        }
    }

    /**
     * Prints the elements of an array.
     *
     * @param arr The array to be printed.
     */
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] unsortedArray = {5, 3, 8, 4, 6};
        System.out.println("Unsorted Array:");
        printArray(unsortedArray);

        // Sort the array using Heap Sort
        heapSort(unsortedArray);

        System.out.println("Sorted Array:");
        printArray(unsortedArray);
    }
}

Explanation of the Code

1. heapSort Method:

   • This method implements the Heap Sort algorithm.

   • It first builds a max-heap from the input array.

   • It then repeatedly extracts the largest element from the heap and places it at the end of the array.

2. heapify Method:

   • This method ensures that the subtree rooted at the given index satisfies the max-heap property.

   • It compares the root with its left and right children and swaps if necessary.

3. printArray Method:

   • This method prints the elements of the array in a readable format.

4. main Method:

   • This is the entry point of the program.

   • It initializes an unsorted array, prints it, sorts it using the heapSort method, and then prints the sorted array.

Time Complexity

• Worst-case, Average-case, and Best-case Time Complexity: O(n log n)

  • Building the heap takes O(n) time.

  • Each extraction and heapify operation takes O(log n) time, and there are n such operations.

Space Complexity

• Space Complexity: O(1)

  • Heap Sort is an in-place sorting algorithm and requires only a constant amount of extra space.

When to Use Heap Sort?

Heap Sort is suitable for:

• Large datasets.

• Situations where a guaranteed O(n log n) performance is required.

• In-place sorting (requires minimal extra memory).

For small datasets or when stability is important, consider using Insertion Sort or Merge Sort.

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works well for integers within a specific range. Unlike comparison-based algorithms like Bubble Sort or Quick Sort, Counting Sort counts the occurrences of each element and uses this information to place elements in their correct sorted position.

What is Counting Sort?

Counting Sort is an efficient algorithm for sorting integers when the range of potential items (the difference between the maximum and minimum values) is not significantly larger than the number of items to be sorted. It works by counting the number of objects that have distinct key values and using arithmetic to determine the positions of each key in the output sequence.

How Counting Sort Works

Let’s break down the steps of Counting Sort with an example. Consider the following unsorted array:

[4, 2, 2, 8, 3, 3, 1]

Step 1: Find the Range of the Input

• Determine the minimum and maximum values in the array.

• For the given array, the minimum value is 1, and the maximum value is 8.

Step 2: Initialize the Count Array

• Create a count array of size (max - min + 1) to store the count of each unique element.

• For the given array, the count array size is 8 - 1 + 1 = 8.

• Initialize all counts to 0.

Count Array: [0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Populate the Count Array

• Traverse the input array and store the count of each element in the count array.

• For the given array:

  • Count of 1: 1

  • Count of 2: 2

  • Count of 3: 2

  • Count of 4: 1

  • Count of 8: 1

Count Array: [1, 2, 2, 1, 0, 0, 0, 1]

Step 4: Modify the Count Array

• Modify the count array to store the cumulative count. This helps in placing the elements in the correct position in the output array.

• For the given array:

  • Cumulative Count Array: [1, 3, 5, 6, 6, 6, 6, 7]

Cumulative Count Array: [1, 3, 5, 6, 6, 6, 6, 7]

Step 5: Build the Output Array

• Traverse the input array from the end to the beginning, and use the cumulative count array to place each element in its correct position in the output array.

• Decrease the count by 1 after placing each element.

Output Array: [1, 2, 2, 3, 3, 4, 8]

Visual Representation of Counting Sort

Initial Array: [4, 2, 2, 8, 3, 3, 1]
Count Array: [1, 2, 2, 1, 0, 0, 0, 1]
Cumulative Count Array: [1, 3, 5, 6, 6, 6, 6, 7]
Output Array: [1, 2, 2, 3, 3, 4, 8]

Implementation of Counting Sort

Here’s the Python code for Counting Sort with detailed comments:

import java.util.Arrays;

public class CountingSort {

    public static int[] countingSort(int[] arr) {
        // Step 1: Find the range of the input
        int max = Arrays.stream(arr).max().getAsInt(); // Find the maximum value in the array
        int min = Arrays.stream(arr).min().getAsInt(); // Find the minimum value in the array
        int range = max - min + 1; // Calculate the range of elements

        // Step 2: Initialize the count array
        int[] count = new int[range]; // Create a count array of size 'range'
        int[] output = new int[arr.length]; // Create an output array to store the sorted elements

        // Step 3: Populate the count array
        for (int num : arr) {
            count[num - min]++; // Increment the count of each element
        }

        // Step 4: Modify the count array to store cumulative counts
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1]; // Calculate cumulative counts
        }

        // Step 5: Build the output array
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i]; // Place the element in the correct position
            count[arr[i] - min]--; // Decrease the count for the element
        }

        return output; // Return the sorted array
    }

    public static void main(String[] args) {
        int[] unsortedArray = {4, 2, 2, 8, 3, 3, 1}; // Input array
        System.out.println("Unsorted Array: " + Arrays.toString(unsortedArray));

        int[] sortedArray = countingSort(unsortedArray); // Perform Counting Sort
        System.out.println("Sorted Array: " + Arrays.toString(sortedArray));
    }
}

Explanation of the Code

1. Step 1: Find the Range of the Input

   • Use Arrays.stream(arr).max().getAsInt() and Arrays.stream(arr).min().getAsInt() to find the maximum and minimum values in the array.

   • Calculate the range as max - min + 1.

2. Step 2: Initialize the Count Array

   • Create a count array of size range to store the count of each unique element.

   • Create an output array of the same size as the input array to store the sorted elements.

3. Step 3: Populate the Count Array

   • Traverse the input array and increment the count of each element in the count array.

4. Step 4: Modify the Count Array

   • Modify the count array to store cumulative counts. This helps in determining the correct position of each element in the output array.

5. Step 5: Build the Output Array

   • Traverse the input array from the end to the beginning.

   • Use the cumulative count array to place each element in its correct position in the output array.

   • Decrease the count for the element after placing it in the output array.

Time Complexity

• Time Complexity: O(n + k)

  • Where n is the number of elements in the input array, and k is the range of the input (i.e., max - min + 1).

• Space Complexity: O(k)

  • Additional space is required for the count array.

When to Use Counting Sort?

• Sorting integers within a specific range.

• When the range of input data (k) is not significantly larger than the number of elements (n).

• When stable sorting is required (relative order of equal elements is preserved).

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that works by processing individual digits of numbers. It sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). Radix Sort is efficient for sorting integers or strings with fixed widths.

What is Radix Sort?

Radix Sort is a stable sorting algorithm that sorts numbers by processing their digits. It uses a subroutine (like Counting Sort) to sort the numbers based on each digit. Radix Sort can be implemented in two ways:

1. Least Significant Digit (LSD) Radix Sort: Starts sorting from the rightmost digit.

2. Most Significant Digit (MSD) Radix Sort: Starts sorting from the leftmost digit.

In this guide, we’ll focus on LSD Radix Sort.

How Radix Sort Works

Let’s break down the steps of Radix Sort with an example. Consider the following unsorted array:

[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Find the Maximum Number

• Determine the maximum number in the array to know the number of digits.

• For the given array, the maximum number is 802, which has 3 digits.

Step 2: Sort by Each Digit

• Perform Counting Sort for each digit, starting from the least significant digit (rightmost) to the most significant digit (leftmost).

Pass 1: Sort by the 1st Digit (Units Place)

• Input Array: [170, 45, 75, 90, 802, 24, 2, 66]

• Sorted Array after 1st Pass: [170, 90, 802, 2, 24, 45, 75, 66]

Pass 2: Sort by the 2nd Digit (Tens Place)

• Input Array: [170, 90, 802, 2, 24, 45, 75, 66]

• Sorted Array after 2nd Pass: [802, 2, 24, 45, 66, 170, 75, 90]

Pass 3: Sort by the 3rd Digit (Hundreds Place)

• Input Array: [802, 2, 24, 45, 66, 170, 75, 90]

• Sorted Array after 3rd Pass: [2, 24, 45, 66, 75, 90, 170, 802]

Visual Representation of Radix Sort

Initial Array: [170, 45, 75, 90, 802, 24, 2, 66]
After 1st Pass (Sort by Units Place): [170, 90, 802, 2, 24, 45, 75, 66]
After 2nd Pass (Sort by Tens Place): [802, 2, 24, 45, 66, 170, 75, 90]
After 3rd Pass (Sort by Hundreds Place): [2, 24, 45, 66, 75, 90, 170, 802]

Implementation of Radix Sort

import java.util.Arrays;

public class RadixSort {

    // A utility function to get the maximum value in the array
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // A function to perform Counting Sort based on the digit represented by exp
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // Output array to store sorted elements
        int[] count = new int[10]; // Count array to store counts of digits (0-9)

        // Step 1: Initialize count array
        Arrays.fill(count, 0);

        // Step 2: Store the count of each digit in the count array
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // Step 3: Modify the count array to store cumulative counts
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Step 4: Build the output array by placing elements in their correct positions
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Step 5: Copy the output array back to the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Main Radix Sort function
    public static void radixSort(int[] arr) {
        // Find the maximum number to know the number of digits
        int max = getMax(arr);

        // Perform Counting Sort for each digit, starting from the least significant digit
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] unsortedArray = {170, 45, 75, 90, 802, 24, 2, 66}; // Input array
        System.out.println("Unsorted Array: " + Arrays.toString(unsortedArray));

        radixSort(unsortedArray); // Perform Radix Sort
        System.out.println("Sorted Array: " + Arrays.toString(unsortedArray));
    }
}

Explanation of the Code

1. getMax(int[] arr):

   • Finds the maximum number in the array to determine the number of digits.

2. countingSort(int[] arr, int exp):

   • Performs Counting Sort on the array based on the digit represented by exp (1 for units place, 10 for tens place, etc.).

   • Uses a count array to store the frequency of each digit (0-9).

   • Modifies the count array to store cumulative counts.

   • Builds the output array by placing elements in their correct positions.

3. radixSort(int[] arr):

   • Calls countingSort for each digit, starting from the least significant digit (LSD) to the most significant digit (MSD).

Time Complexity

• Time Complexity: O(d * (n + k))

  • Where n is the number of elements, k is the range of digits (0-9), and d is the number of digits in the maximum number.

• Space Complexity: O(n + k)

  • Additional space is required for the output array and the count array.

When to Use Radix Sort?

• Sorting integers or fixed-length strings.

• When the range of digits (k) is small (e.g., 0-9 for base 10 numbers).

• When stable sorting is required (relative order of equal elements is preserved).

Algorithm Comparison