Merge Sort

Merge Sort is a popular comparison-based sorting algorithm known for its efficiency and stability. It employs a divide-and-conquer strategy to sort an array or list by recursively dividing it into smaller sub-arrays until each sub-array consists of a single element, then merging those sub-arrays to produce a sorted array.

The basic idea behind merge sort is this: it tends to be a lot easier to sort two smaller, sorted lists rather than sorting a single large, unsorted one.

How Merge Sort Works

1. Divide Phase: Divide the unsorted array into smaller sub-arrays until each sub-array has only one element.

2. Conquer Phase: Recursively merge adjacent sub-arrays to produce new sorted sub-arrays until there is only one sorted array remaining.

3. Merge Phase: Repeatedly merge sorted sub-arrays to generate larger, more sorted sub-arrays until the entire array is sorted.

Example:
Input: N = 5, array[] = {5,1,7,3,2,8,6,4}
Output: 5,1,7,3,2,8,6,4
Explanation: After sorting we get 1,2,3,4,5,6,7,8

Okay, now we’re down to the smallest possible subproblem: eight lists, and each has one, sorted item within it. Now, we just need to merge two lists together. We’ll merge each sorted list together with its neighbor. When we merge them, we’ll check the first item in each list, and combine the two lists together so that every element is in the correct, sorted order.

Easy-peasy! We got this.

Great! Once we started merging two lists together, we didn’t have to think too much more when it came to merging those two sorted sublists, did we? We used the same technique to merge lists with four items as we did when we merged lists with only one item.

A mergeSort function ultimately has two functions inside of it:

1. a merge function, which actually combines two lists together and sorts them in the correct order

2. and a mergeSort function, which will continue to split the input array again and again, recursively, and will also call merge again and again, recursively.

Pseudocode

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
 

Advantages

• Offers consistent, optimal performance across different datasets.
• Preserves stability as equal elements retain their original order.
• Suitable for sorting linked lists.

Disadvantages

• Requires additional memory space for merging.
• Slower for small datasets compared to other sorting algorithms like Insertion Sort or Bubble Sort.