Merge Sort

Merge Sort is a comparison-based, divide-and-conquer sorting algorithm.
It works by dividing the input array into smaller subarrays, sorting them individually, and then merging them back together to form a final sorted array.

Key Points:

• Divide and Conquer Approach:
  It splits the array into two halves again and again until each subarray has only one element (which is already sorted).
• Recursive Process:
  The sorting happens recursively. It keeps dividing the array until base case (1 element) is reached, then starts merging in sorted order.
• Merging Step:
  The real sorting happens in this step where two sorted subarrays are combined into one sorted array.

Why is it Called “Merge” Sort?

Because it focuses on merging sorted subarrays, not just swapping like bubble or selection sort. This merging step is the heart of the algorithm.

Working of Merge Sort (Step-by-Step)

Merge Sort is a divide-and-conquer algorithm. It works in three main steps:

1. Divide:
   Recursively divide the array into two halves until each subarray contains only one element.
2. Conquer (Sort):
   Recursively sort each of the two halves.
3. Combine (Merge):
   Merge the sorted halves to produce a new sorted array.

Example:

• Let’s sort this array:
  [38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the array

• [38, 27, 43, 3, 9, 82, 10]
• → [38, 27, 43] and [3, 9, 82, 10]
• → [38], [27, 43] and [3, 9], [82, 10]
• → [27], [43] and [3], [9], [82], [10]

Step 2: Sort and merge each part

• → Merge [27], [43] → [27, 43]
• → Merge [38], [27, 43] → [27, 38, 43]
• → Merge [3], [9] → [3, 9]
• → Merge [82], [10] → [10, 82]
• → Merge [3, 9], [10, 82] → [3, 9, 10, 82]

Step 3: Final Merge

• → Merge [27, 38, 43] and [3, 9, 10, 82]
• → Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]

Merge Sort Python code:

function mergeSort(arr):

    if len(arr) > 1:

        mid = len(arr) // 2

        left = arr[:mid]

        right = arr[mid:]

        mergeSort(left)

        mergeSort(right)

        merge (left, right, arr)

Time Complexity of Merge Sort:

         Space Complexity:

• O(n)
  (Extra space is required to merge the divided arrays)

          Note:

Merge Sort is a divide and conquer algorithm. It’s efficient and consistent with time complexity O (n log n) in all cases. It is stable and preferred for large datasets, though it needs additional memory.