Day 17: Insertion Sort and Merge Sort

Sorting algorithms are crucial for organizing data efficiently, and in this post, we’ll explore two important sorting methods: Insertion Sort and Merge Sort. We will cover their explanations, implementations in Java, time complexity analyses, and example problems.

What is Insertion Sort?

Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted array one element at a time. It works similarly to how you might sort playing cards in your hands: you take one card and insert it into the correct position in the already sorted section of cards.

Implementation in Java

Here’s how to implement Insertion Sort in Java:

javaCopy codepublic class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Move elements greater than key to one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Time Complexity Analysis

• Best Case: O(n) – This occurs when the array is already sorted. Only one pass is needed to confirm this.
• Average Case: O(n²) – On average, the algorithm requires multiple passes to sort the data.
• Worst Case: O(n²) – This occurs when the array is sorted in reverse order.

Insertion Sort is efficient for small datasets and performs well when the input array is partially sorted.

What is Merge Sort?

Merge Sort is a more advanced sorting algorithm that follows the divide-and-conquer paradigm. It divides the input array into halves, recursively sorts them, and then merges the sorted halves to produce the final sorted array.

Implementation in Java

Here’s how to implement Merge Sort in Java:

javaCopy codepublic class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) return;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        for (int i = 0; i < mid; i++) left[i] = arr[i];
        for (int i = mid; i < arr.length; i++) right[i - mid] = arr[i];

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }
        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Time Complexity Analysis

• Best Case: O(n log n) – Merge Sort consistently divides the array and merges it, regardless of initial order.
• Average Case: O(n log n) – The performance remains logarithmic on average due to the divide-and-conquer approach.
• Worst Case: O(n log n) – The worst case also maintains O(n log n) complexity.

Merge Sort is efficient for large datasets and is often used in external sorting algorithms where large amounts of data need to be sorted.

Example Problems

1. Insertion Sort Example: Given an array of integers: {5, 2, 9, 1, 5, 6}, using Insertion Sort will transform it to {1, 2, 5, 5, 6, 9}.
2. Merge Sort Example: Given an array of integers: {38, 27, 43, 3, 9, 82, 10}, using Merge Sort will result in {3, 9, 10, 27, 38, 43, 82}.

Conclusion

Insertion Sort and Merge Sort are fundamental sorting algorithms, each with its strengths and use cases. While Insertion Sort is simple and efficient for small datasets, Merge Sort excels in handling larger datasets efficiently.

In our next post, we will explore Quick Sort, another powerful sorting algorithm. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB