Merge Sort

Merge sort is a sorting method that uses the divide-and-conquer strategy. It works by splitting the input array into smaller subarrays, sorting those subarrays, and then merging them back together to get the sorted array.

Simply put, merge sort divides the array into two parts, sorts each part, and then merges the sorted parts back together. This is repeated until the whole array is sorted.

How does Merge Sort work?

Merge sort is a well-known sorting method because it is efficient and stable. It uses the divide-and-conquer approach to sort an array of elements.

Here’s a simple explanation of how merge sort works:

1. Divide: Split the list or array into two halves repeatedly until it can't be divided anymore.

2. Conquer: Sort each subarray individually using the merge sort method.

3. Merge: Combine the sorted subarrays back together in order. This continues until all elements from both subarrays are merged.

To understand the working of the merge sort algorithm, let's take an unsorted array. It will be easier to understand the merge sort via an example.

According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look like -

Now, the array is completely sorted.

Complexity Analysis of Merge Sort:

Time Complexity:

• Best Case: O(n log n), When the array is already sorted or nearly sorted.

• Average Case: O(n log n), When the array is randomly ordered.

• Worst Case: O(n log n), When the array is sorted in reverse order.

Space Complexity: O(n), Additional space is required for the temporary array used during merging.

Advantages of Merge Sort:

• Stability: Merge sort is a stable sorting algorithm. This means it keeps the relative order of equal elements in the input array. For example, if two elements are equal, their order will remain the same in the sorted array as it was in the input array. This is particularly useful in scenarios where the order of equal elements carries meaning or additional information.

• Guaranteed worst-case performance: Merge sort has a worst-case time complexity of O(N log N). This means that even in the worst-case scenario, such as when the array is sorted in reverse order, merge sort will still perform efficiently. This predictable performance is crucial for applications that require consistent and reliable sorting times, especially when dealing with large datasets.

• Simple to implement: The divide-and-conquer approach used in merge sort is straightforward and easy to understand. The algorithm can be broken down into simple steps: dividing the array into smaller subarrays, sorting those subarrays, and then merging them back together. This simplicity makes merge sort an excellent choice for educational purposes and for developers who need a reliable sorting algorithm without complex implementation details.

Disadvantage of Merge Sort:

• Space complexity: Merge sort requires additional memory to store the merged subarrays during the sorting process. Specifically, it needs extra space equivalent to the size of the array being sorted. This additional memory usage can be a significant drawback in environments with limited memory resources, such as embedded systems or applications running on devices with constrained memory.

• Not in-place: Merge sort is not an in-place sorting algorithm, meaning it does not sort the array within the original array's memory space. Instead, it requires additional memory to store the sorted data temporarily. This can be a disadvantage in applications where memory usage is a concern, as it increases the overall memory footprint of the sorting process. In contrast, in-place sorting algorithms like quicksort or heapsort do not require extra memory for the sorted data, making them more suitable for memory-constrained environments.