3-Way Merge Sort – Sorting Algorithm

3-Way Merge Sort

3-Way Merge Sort is a variant of the classic Merge Sort algorithm. Instead of dividing the array into two subarrays, it divides the array into three subarrays, recursively sorts them, and then merges them into a single sorted array. This approach aims to improve the efficiency of Merge Sort by reducing the recursive depth.

---

1. How It Works

1. Divide:

   • Split the array into three nearly equal parts.

2. Conquer:

   • Recursively apply the 3-Way Merge Sort on each part.

3. Combine:

   • Merge the three sorted subarrays into one sorted array.

---

2. Key Characteristics

• Time Complexity:

  • Average and worst-case complexity: O(nlog⁡3n)O(n log_3 n), slightly better than Merge Sort (O(nlog⁡2n)O(n log_2 n)).

• Space Complexity:

  • Requires O(n)O(n) additional space for merging.

• Stability:

  • Like traditional Merge Sort, it is a stable sorting algorithm.

• Recursive Depth:

  • The depth of recursion is reduced compared to traditional Merge Sort due to dividing the array into three parts instead of two.

---

3. Step-by-Step Example

Example Array: [9, 7, 5, 3, 1, 8, 6, 4, 2]

1. Divide:

   • Split the array into three parts:
     • Left: [9, 7, 5]
     • Middle: [3, 1, 8]
     • Right: [6, 4, 2]

2. Sort Each Part:

   • Left → [5, 7, 9]
   • Middle → [1, 3, 8]
   • Right → [2, 4, 6]

3. Merge:

   • Combine the sorted parts into a single sorted array:
     • Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

---

4. Advantages and Disadvantages

Advantages:

• Improved Efficiency: Reduces the recursion depth, leading to potentially faster execution in some cases.
• Stability: Maintains the relative order of identical elements.

Disadvantages:

• Increased Complexity: Merging three arrays is more complex than merging two.
• Memory Usage: Requires additional space for merging.

---

5. Java Implementation

import java.util.Arrays;
public class ThreeWayMergeSort {
    // Main function to perform 3-way merge sort
    public static void threeWayMergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        // Step 1: Divide the array into three parts
        int third = arr.length / 3;
        int[] left = Arrays.copyOfRange(arr, 0, third);
        int[] middle = Arrays.copyOfRange(arr, third, 2 * third);
        int[] right = Arrays.copyOfRange(arr, 2 * third, arr.length);
        // Step 2: Recursively sort each part
        threeWayMergeSort(left);
        threeWayMergeSort(middle);
        threeWayMergeSort(right);
        // Step 3: Merge the three sorted parts
        merge(arr, left, middle, right);
    }
    // Helper function to merge three sorted arrays
    private static void merge(int[] arr, int[] left, int[] middle, int[] right) {
        int i = 0, j = 0, k = 0, l = 0;
        while (i < left.length && j < middle.length && k < right.length) {
            if (left[i] <= middle[j] && left[i] <= right[k]) {
                arr[l++] = left[i++];
            } else if (middle[j] <= left[i] && middle[j] <= right[k]) {
                arr[l++] = middle[j++];
            } else {
                arr[l++] = right[k++];
            }
        }
        while (i < left.length && j < middle.length) {
            arr[l++] = (left[i] <= middle[j]) ? left[i++] : middle[j++];
        }
        while (j < middle.length && k < right.length) {
            arr[l++] = (middle[j] <= right[k]) ? middle[j++] : right[k++];
        }
        while (i < left.length && k < right.length) {
            arr[l++] = (left[i] <= right[k]) ? left[i++] : right[k++];
        }
        while (i < left.length) {
            arr[l++] = left[i++];
        }
        while (j < middle.length) {
            arr[l++] = middle[j++];
        }
        while (k < right.length) {
            arr[l++] = right[k++];
        }
    }
    // Main driver
    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 3, 1, 8, 6, 4, 2};
        System.out.println("Original Array: " + Arrays.toString(arr));
        threeWayMergeSort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python Implementation

def three_way_merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # Step 1: Divide the array into three parts
    third = len(arr) // 3
    left = arr[:third]
    middle = arr[third:2*third]
    right = arr[2*third:]
    # Step 2: Recursively sort each part
    left = three_way_merge_sort(left)
    middle = three_way_merge_sort(middle)
    right = three_way_merge_sort(right)
    # Step 3: Merge the three sorted parts
    return merge(left, middle, right)
# Helper function to merge three sorted arrays
def merge(left, middle, right):
    result = []
    i = j = k = 0
    while i < len(left) and j < len(middle) and k < len(right):
        if left[i] <= middle[j] and left[i] <= right[k]:
            result.append(left[i])
            i += 1
        elif middle[j] <= left[i] and middle[j] <= right[k]:
            result.append(middle[j])
            j += 1
        else:
            result.append(right[k])
            k += 1
    while i < len(left) and j < len(middle):
        result.append(left[i] if left[i] <= middle[j] else middle[j])
        i += (left[i] <= middle[j])
        j += (left[i] > middle[j])
    while j < len(middle) and k < len(right):
        result.append(middle[j] if middle[j] <= right[k] else right[k])
        j += (middle[j] <= right[k])
        k += (middle[j] > right[k])
    while i < len(left) and k < len(right):
        result.append(left[i] if left[i] <= right[k] else right[k])
        i += (left[i] <= right[k])
        k += (left[i] > right[k])
    result.extend(left[i:])
    result.extend(middle[j:])
    result.extend(right[k:])
    return result
# Example usage
if __name__ == "__main__":
    arr = [9, 7, 5, 3, 1, 8, 6, 4, 2]
    print("Original Array:", arr)
    sorted_arr = three_way_merge_sort(arr)
    print("Sorted Array:", sorted_arr)

---

7. Applications

• Special Cases: Useful when reducing recursion depth is critical.
• Theoretical Interest: Often studied for its optimization potential over traditional Merge Sort.

While 3-Way Merge Sort offers theoretical advantages, it is less commonly used in practice due to the increased complexity of merging three arrays.