Learn Merge Sort in 13 minutes ?

Introduction

Hey, what's going on everybody? It's your bro! I hope you're doing well. In this article, we're going to discuss the Merge Sort algorithm in computer science. So sit back, relax, and enjoy the show.

Introduction

Merge Sort is a divide and conquer algorithm. Basically, what we do is pass an array as an argument to the Merge Sort function. This function divides the array into two sub-arrays: a left array and a right array. These sub-arrays receive elements from the original array. Since Merge Sort is a recursive function, it will further divide these sub-arrays until their size is one. This sets the stage for sorting and merging.

Overview of the Algorithm

Merge Sort works as follows:

1. Pass an array as an argument.
2. Divide the array into two sub-arrays.
3. Recursively call Merge Sort, passing in the sub-arrays.
4. Divide these sub-arrays again into smaller sub-arrays.
5. Stop when each sub-array has a size of one.
6. Merge these one-element arrays into sorted arrays.

Detailed Breakdown

Step-by-Step Process

1. Initial Step: Pass the array to the Merge Sort function.
2. Divide: Split the array into two halves.
3. Recursive Division: Recursively apply Merge Sort to these halves until single-element arrays are achieved.
4. Merge Function: Combine these single-element arrays into a sorted array.

Merge Function

This function takes three arguments: the left sub-array, the right sub-array, and the original array. It sorts and merges these sub-arrays back into the original array.

Practical Execution

When executed, the Merge Sort algorithm tackles sub-arrays one branch at a time, starting with the leftmost branch and moving towards the right.

Runtime Complexity

The Merge Sort algorithm has a runtime complexity of O(n log n), running in quasi-linear time. This makes the algorithm faster for large data sets compared to insertion sort, selection sort, and bubble sort. However, Merge Sort uses more space because it creates new sub-arrays, unlike sorting algorithms that sort in place.

Coding Merge Sort

Here’s how you can implement Merge Sort in code:

public class MergeSort (

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7);
        System.out.println("Given Array");
        printArray(array);

        MergeSort ob = new MergeSort();
        ob.mergeSort(array, 0, array.length - 1);

        System.out.println("\nSorted array");
        printArray(array);
    }

    void mergeSort(int arr[], int left, int right) (
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        )
    }

    void merge(int arr[], int left, int mid, int right) (
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            ) else (
                arr[k] = R[j];
                j++;
            )
            k++;
        }

        while (i < n1) (
            arr[k] = L[i];
            i++;
            k++;
        )

        while (j < n2) (
            arr[k] = R[j];
            j++;
            k++;
        )
    }

    static void printArray(int arr[]) (
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    )
}

Keywords

• Merge Sort
• Divide and Conquer
• Recursive Function
• Runtime Complexity
• O(n log n)

FAQs

What is Merge Sort?

Merge Sort is a divide and conquer algorithm that recursively divides an array into sub-arrays, sorts them, and then merges them back into a sorted array.

What is the time complexity of Merge Sort?

The time complexity of Merge Sort is O(n log n), making it efficient for large data sets.

Why does Merge Sort use more space?

Merge Sort uses more space because it creates new sub-arrays to store elements, unlike sorting algorithms that sort in place.

What is a recursive function in the context of Merge Sort?

A recursive function is a function that calls itself. In Merge Sort, the function repeatedly calls itself to divide the array into smaller sub-arrays until they can't be divided further.