Can Some One Please Help Me With This Code , I Need To Divide And Conquer By 3! I Mean I Need To Split The Array By 3 Not By 2 , I Wrote This Code But It Still Give Me Error “StackOverFlow Error ” Someone Please Edit It And Tell Me What Is The Problem :)
// Can some one please help me with this code , i need to divide and conquer by 3! i mean i need to split the array by 3 not by 2 , i wrote this code but it still give me error “StackOverFlow error ” someone please edit it and tell me what is the problem 🙂
public class divided_by_three{
// Main function that sorts arr[l..r] using
// merge()
void merge_sort(int arr[], int p, int r)
{
if (p < r)
{
// Find the middle point
int q = (p+r)/3;
// Sort first and second halves
merge_sort(arr , p , q);
merge_sort(arr , (q+1) , (2*q));
merge_sort(arr , ((2*q)+1) , r);
// Merge the sorted halves
merge(arr, p, q, r);
}
}
void merge(int arr[], int p, int q, int r)
{
// Find sizes of two subarrays to be merged
int n1 = q – p + 1; // n1 = 2-0+1 = 3
int n2 = (2*q) – q ;Â Â // n2= 2*2 – 2 = 2
int n3 = r – (2*q); // 7 – 2*2 = 3
/* Create temp arrays */
int L[] = new int [n1+1]; // it will take 4 values
int M[] = new int [n2+1]; // it will take 3 values;
int R[] = new int [n3+1]; // it will take 4 values
/*Copy data to temp arrays*/
for (int i=0; i<n1; i++)
L[i] = arr[p + i];
for (int i=0; i<n2; i++)
M[i] = arr[q+1 + i];
for (int j=0; j<n3; j++)
R[j] = arr[(2*q) + 1+ j];
L[n1]=Integer.MAX_VALUE;
M[n2]=Integer.MAX_VALUE;
R[n3]=Integer.MAX_VALUE;
int i = 0, j = 0 , m=0;
for(int k=p; k<=r ; k++)
{
if (L[i] <= M[m])
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
p++;
}
}
else
{
if(M[m] <= R[j])
{
arr[k] = M[m];
j++;
}
else
{
arr[k] = R[j];
p++;
}
}
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; i++)
System.out.print(arr[i] + ” “);
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = {5,2,4,7,1,3,2,6};
System.out.println(“Given Array”);
printArray(arr);
divided_by_three ob = new divided_by_three();
ob.merge_sort(arr, 0, arr.length-1);
System.out.println(“\nSorted array”);
printArray(arr);
}
}