Merge Sort – Data Structure and Algorithms Tutorials

Merge Sort is a divide and conquer algorithm that efficiently sorts an array or list. It was invented by John von Neumann in 1945 and is widely used because of its predictable O(n log n) time complexity, which makes it suitable for large datasets.

Concept of Merge Sort:

Merge Sort works by recursively dividing the array into two halves, sorting each half, and then merging the sorted halves back together. Here’s how it works in a step-by-step manner:

Steps in Merge Sort:

1. Divide:
   • If the array has more than one element, split it into two halves.
   • Recursively continue dividing the array until you reach arrays of size 1, which are trivially sorted.
2. Conquer:
   • Once the array is divided into single-element arrays, start merging these subarrays back together.
   • During the merge process, you combine two sorted arrays into a single sorted array. This merging step ensures that the combined array remains sorted.
3. Combine:
   • The merge operation is performed by comparing the elements of the two subarrays and placing the smaller element first in the new array, continuing this process until both subarrays are fully merged.

Merge Sort Algorithm:

Pseudocode:

Time Complexity:

• Best, Average, and Worst Case: O(n log n)
  • Regardless of how sorted the array is, Merge Sort always divides the array into halves and performs a merge on each pair of subarrays.
  • The dividing process takes O(log n) time, and merging two halves takes O(n) time.
  • So, the overall complexity is O(n log n).
• Space Complexity: O(n)
  • Merge Sort requires extra space to store the two halves during the merge process. Hence, it is not an in-place sorting algorithm like QuickSort.

Advantages of Merge Sort:

1. Stable Sort: Merge Sort is a stable sorting algorithm, which means that elements with equal keys will maintain their original order in the sorted list.
2. Time Complexity: It always runs in O(n log n) time, making it very efficient for large datasets.
3. Works well with linked lists: Merge Sort can be implemented on linked lists efficiently.

Disadvantages of Merge Sort:

1. Space Complexity: It requires extra space for the subarrays being merged, which makes it less space-efficient than in-place sorting algorithms like QuickSort or Bubble Sort.
2. Slower than QuickSort in practice: While Merge Sort has a guaranteed O(n log n) time complexity, QuickSort is often faster in practice due to better cache performance and fewer memory accesses.

Example of Merge Sort:

Let’s consider an example of sorting an array using Merge Sort.

Input Array: [38, 27, 43, 3, 9, 82, 10]

1. Divide:
   • First, divide the array into two halves: [38, 27, 43, 3] and [9, 82, 10].
   • Recursively split these halves until single-element arrays are obtained.
2. Merge:
   • Merge [38] and [27] to form [27, 38].
   • Merge [43] and [3] to form [3, 43].
   • Continue merging until the entire array is sorted.

Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]

Merge Sort in Python:

Here’s a Python implementation of Merge Sort:

Output:

Conclusion:

Merge Sort is an efficient, stable, and predictable sorting algorithm with an O(n log n) time complexity. It is particularly effective when dealing with large datasets and linked lists. However, it requires extra space for merging, making it less space-efficient than some other algorithms like QuickSort or HeapSort. It is commonly used in applications where the stability of the sort is important, or when working with large datasets that don’t fit into memory (like external sorting).