Three way merge sort problem not sorting correctly

I've been working on this three way merge sort algorithm which I based off of my normal merge sort code; however, it isn't sorting correctly and so I believe there might be a minor mistake in my code. Any help please? I've been looking into the code for 3 hours trying to find the problem but it has proven difficult.

public class TriMergeSort {
void merge(int arr[], int low, int mid1, int mid2, int high) { 
int sizeA = mid1 - low + 1; 
int sizeB =  mid2 - mid1;
int sizeC = high - mid2;
int A[] = new int[sizeA]; 
int B[] = new int[sizeB]; 
int C[] = new int[sizeC];
for (int i = 0; i < sizeA; i++) 
A[i] = arr[low + i]; 
for (int j = 0; j < sizeB; j++) 
B[j] = arr[mid1 + j + 1]; 
for (int x = 0; x < sizeC; x++) 
C[x] = arr[mid2 + x + 1];
int i = 0, j = 0, x = 0; 
int k = low; 
while (i < sizeA && j < sizeB && x < sizeC) {
if (A[i] < B[j] && A[i] < C[x]) { 
arr[k] = A[i]; 
i++; 
} else
if (A[i] >= B[j] && B[j] < C[x]) { 
arr[k] = B[j]; 
j++; 
} else
if (A[i] > C[x] && B[j] >= C[x]) { 
arr[k] = C[x]; 
x++; 
} 
k++; 
} 
while (i < sizeA) { 
arr[k] = A[i]; 
i++; 
k++; 
} 
while (j < sizeB) { 
arr[k] = B[j]; 
j++; 
k++; 
} 
while (x < sizeC) { 
arr[k] = C[x]; 
x++; 
k++; 
}
} 
void sort(int arr[], int low, int high) { 
if (low < high) {  
int mid1 = low + ((high - low) / 3); 
int mid2 = low + 2 * ((high - low) / 3) + 1;
sort(arr, low, mid1); 
sort(arr, mid1 + 1, mid2); 
sort(arr, mid2 + 1, high);
merge(arr, low, mid1, mid2, high); 
} 
} 
static void print(int arr[]) { 
int n = arr.length; 
for (int i = 0; i < n; ++i) 
System.out.print(arr[i] + " "); 
System.out.println(); 
} 
public static void main(String args[]) { 
int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 
TriMergeSort test = new TriMergeSort(); 
test.sort(arr, 0, arr.length - 1); 
print(arr); 
}
} 

The code posted in the question works fine. You did not post the 3-way merge code you have problems with.

Note that instead of passing high as the index to the last item in the slice to sort, you should pass the index of the first element beyond the slice. This allows for simpler code, without confusing and error prone +1/-1 adjustments.

Here is a modified version:

public class MergeSort { 

    void merge(int arr[], int low, int mid, int high) { 
        int sizeA = mid - low; 
        int sizeB = high - mid; 

        int A[] = new int[sizeA]; 
        int B[] = new int[sizeB]; 

        for (int i = 0; i < sizeA; i++) 
            A[i] = arr[low + i]; 
        for (int j = 0; j < sizeB; j++) 
            B[j] = arr[mid + j]; 

        int i = 0, j = 0; 
        int k = low; 
        
        while (i < sizeA && j < sizeB) { 
            if (A[i] <= B[j]) { 
                arr[k++] = A[i++]; 
            } else { 
                arr[k++] = B[j++]; 
            } 
        } 

        while (i < sizeA) {
            arr[k++] = A[i++];
        } 

        while (j < sizeB) { 
            arr[k++] = B[j++];
        } 
    } 

    void sort(int arr[], int low, int high) { 
        if (high - low >= 2) {  
            int mid = low + (high - low) / 2; 
            sort(arr, low, mid); 
            sort(arr, mid, high); 
            merge(arr, low, mid, high); 
        } 
    } 

    static void print(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(); 
    } 

    public static void main(String args[]) { 
        int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12, 10, 59 }; 
        MergeSort test = new MergeSort(); 
        test.sort(arr, 0, arr.length); 
        print(arr); 
    } 
}

To convert this into a 3-way merge version, sort3 must follow these steps:

• split the range into 3 slices instead of 2. The first slice runs from low to mid1 = low + (high - low)/3 excluded, the second from mid1 to mid2 = low + (high - low)*2/3 excluded and the third from mid2 to high excluded.
• sort each of the 3 subslices recursively
• call merge3(arr, low, mid1, mid2, high)
  • make copies of the 3 subslices
  • write a loop for 3 index values running the 3 slices until one of them is exhausted
  • write 3 loops for the 2 remaining slices (A and B) or (B and C) or (A and C),
  • write 3 loops to copy the remaining elements from the remaining slice, A, B or C

EDIT: the merge function in your TriMergeSort class is missing the 3 loops that merge 2 slices once one of the 3 initial slices is exhausted. This explains why the array does not get properly sorted. After the 3-way merge loop, you should have:

    while (i < sizeA && j < sizeB) {
...
}
while (i < sizeA && x < sizeC) {
...
}
while (j < sizeB && x < sizeC) {
...
}

To avoid all these repeated loops, you could combine tests on the index values into a single loop body:

public class TriMergeSort {

    void merge(int arr[], int low, int mid1, int mid2, int high) { 
        int sizeA = mid1 - low; 
        int sizeB = mid2 - mid1;
        int sizeC = high - mid2;

        int A[] = new int[sizeA]; 
        int B[] = new int[sizeB]; 
        int C[] = new int[sizeC];

        for (int i = 0; i < sizeA; i++) 
            A[i] = arr[low + i]; 
        for (int j = 0; j < sizeB; j++) 
            B[j] = arr[mid1 + j]; 
        for (int k = 0; k < sizeC; k++) 
            C[k] = arr[mid2 + k];

        int i = 0, j = 0, k = 0;
        
        while (low < high) {
            if (i < sizeA && (j >= sizeB || A[i] <= B[j])) {
                if (k >= sizeC || A[i] <= C[k]) {
                    arr[low++] = A[i++];
                } else {
                    arr[low++] = C[k++];
                }
            } else {
                if (j < sizeB && (k >= sizeC || B[j] <= C[k])) {
                    arr[low++] = B[j++];
                } else {
                    arr[low++] = C[k++];
                }
            }
        } 
    } 

    void sort(int arr[], int low, int high) { 
        if (high - low >= 2) {  
            int mid1 = low + (high - low) / 3; 
            int mid2 = low + (high - low) * 2 / 3;
            sort(arr, low, mid1); 
            sort(arr, mid1, mid2); 
            sort(arr, mid2, high);
            merge(arr, low, mid1, mid2, high); 
        } 
    } 

    static void print(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(); 
    } 

    public static void main(String args[]) { 
        int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 
        TriMergeSort test = new TriMergeSort(); 
        test.sort(arr, 0, arr.length); 
        print(arr); 
    }
}

The while loop above can be further simplified but somewhat less readable as:

    while (low < high) {
if (i < sizeA && (j >= sizeB || A[i] <= B[j])) {
arr[low++] = (k >= sizeC || A[i] <= C[k]) ? A[i++] : C[k++];
} else {
arr[low++] = (j < sizeB && (k >= sizeC || B[j] <= C[k])) ? B[j++] : C[k++];
}
} 

And even one step further:

    while (low < high) {
arr[low++] = (i < sizeA && (j >= sizeB || A[i] <= B[j])) ?
((k >= sizeC || A[i] <= C[k]) ? A[i++] : C[k++]) :
(j < sizeB && (k >= sizeC || B[j] <= C[k])) ? B[j++] : C[k++];
}