Question

Re-write this method using iteration ONLY

JAVA

class Main {

public static void merge(int arr[], int l, int m, int r)

{

int n1 = m - l + 1;

int n2 = r-m;

int left[] = new int[n1];

int right[] = new int[n2];

for (int i = 0; i < n1; ++i)

left[i] = arr[l + i];

for (int j = 0; j < n2; ++j)

right[j] = arr[m + 1 + j];

int i=0; //left

int j=0; // right

int k=l; // main

while( i<n1 && j<n2){

if(left[i]<=right[j]){

arr[k] = left[i];

i++;

}

else{

arr[k] = right[j];

j++;

}

k++;

}

while(i<n1){

arr[k] = left[i];

i++;

k++;

}

while(j<n2){

arr[k] = right[j];

j++;

k++;

}

}

static void sort(int arr[], int l, int r) {

if(l>=r){

return;

}

if(l<r){

int m = (l+r)/2;

//call the left part divide

sort(arr, l, m);

//call the right to divide

sort(arr, m+1, r);

//merge left and right

merge(arr, l,m,r);

}

}

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[])

{ // 2 3.

int arr[] = { 5,7,6,3 , 2,4,1 };

//main array = 1,2,3,4,5, 6, 7

// left 1,3,6,7

// right 2,4,5

// arr = 1,3,6,7,2,4,5

System.out.println("Given Array");

printArray(arr);

sort(arr, 0, arr.length - 1);

System.out.println("\nSorted array");

printArray(arr);

}

}

Answer 1

// below is java code , modified over your code

class Main {

   static void sort(int arr[],int low , int n)
   {
       int csize,lf;
      
       for (csize = 1; csize <= n; csize = 2*csize)
       {
       for (lf = 0; lf < n;lf =lf+ 2*csize)
           {
               int mid = Math.min(lf + csize - 1, n);
      
               int re = Math.min(lf + 2*csize - 1, n);
               merge(arr, lf, mid, re);
           }
       }
   }
  
  
   static void merge(int arr[], int l, int m, int r)
   {
       int n1 = m - l + 1;

       int n2 = r-m;

       int left[] = new int[n1];

       int right[] = new int[n2];

       for (int i = 0; i < n1; ++i)

       left[i] = arr[l + i];

       for (int j = 0; j < n2; ++j)

       right[j] = arr[m + 1 + j];

       int i=0; //left

       int j=0; // right

       int k=l; // main

       while( i<n1 && j<n2){

       if(left[i]<=right[j]){

       arr[k] = left[i];

       i++;

       }

       else{

       arr[k] = right[j];

       j++;

       }

       k++;

       }

       while(i<n1){

       arr[k] = left[i];

       i++;

       k++;

       }

       while(j<n2){

       arr[k] = right[j];

       j++;

       k++;

       }

   }
  

   static void printArray(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[])

   { // 2 3.

   int arr[] = { 5,7,6,3 , 2,4,1 };

   //main array = 1,2,3,4,5, 6, 7

   // left 1,3,6,7

   // right 2,4,5

   // arr = 1,3,6,7,2,4,5

   System.out.println("Given Array");

   printArray(arr);

   sort(arr, 0, arr.length -1);

   System.out.println("\nSorted array");

   printArray(arr);

   }
}

//output