CODEWITHSUNDEEP
algorithmsortingmergemergesortn-way-merge
Ka Mal
Ka Mal

Reputation: 145

Implement algorithm to merge sorted arrays and return it

I have to implement a Java program called Merge.java which contain the following implementation of algorithm:

public class Merge {

    int k = 2; int n = 4;
//generate a 2-dimensional array data with dimension k × n 
int[][] data = new int[k][n];
    int size = k*n;

//implementing merge procedure for merge sort   

    public static int[] merge(int data[][]){
 // First, creating a new array to store the single sorted array
        int res[] = new int[12];

How can I then traverse through the arrays and compare their elements one by one and insert them in the new array (res) in sorted order and is this the right way as per question?

return res ;
}
    public static void printArray(int[] arr){
            for(int i : arr) {
                System.out.printf("%d ", i);
            }
    System.out.printf("n");
}

public static void main(String[]args){
Merge obj = new Merge();
int[][] array = new int[][]{{12, 8, 1, 5},{ 10, 3, 4, 23}};
int [] finalSorted = merge(array);
printArray(finalSorted);
 }
}

Edited to add:

Was both helpful..cheers.. this is what I got so far:

However my program should return this in 2-Dimension and arrays can be more than two: Program should generate a 2-dimensional array data with dimension k × n storing k sorted arrays of randomly generated integers of length n. Each algorithm should take data as input and merge all k lists into one single array result of length k × n. What would be next step? 

//merge method take takes two arrays as parameters and returns the merge array

public int[]  merge(int[] array1 , int [] array2){
int i=0,j=0,k = 0;
int m=array1.length; 
int n=array2.length ;   

// declaring a to be returned array after merging those two array1 & array2     

int[] mergedArray = new int[m+n];


//comparing between two arrays , write it and compare next element and so on

 while(i< m && j<n){
            if(array1[i]<= array2[j]){

// if first element of array1 is <= then array2 then place array1 element in the mergedArray and viceversa

mergedArray[k] = array1[i];
                    i++;
            }else{
                mergedArray[j]=array2[j]; // opposite of above 
                j++;
            } 
            k++ ;
        }

// when run out of elements from one or other array, just write all the elements from the other

if(i<m){
            for(int p=i ; p<m ; p++){
                mergedArray[k] = array1[p];
                k++;
            }
        } else {
            for(int p=j ; p<n ; p++){
                mergedArray[k]=array2[p];
                k++;
            }
        }
        return mergedArray; 
    }
}

Upvotes: -1

Views: 723

Answers (2)

Erick G. Hagstrom
Erick G. Hagstrom

Reputation: 4945

Rather than just post the answer, let me give you some pointers in the right direction.

First, you'll need a merge() method that takes two arrays as parameters and returns the merged array. That means that the returned array should be declared and allocated inside the merge() method itself.

Then it's just a matter of looking at the two arrays, element by element. If the current element from a is less than the current element of b, write it and get the next element from a. If the current element from b is less than the current element from a, write it and get the next element from b. And when you run out of elements from one or the other array, just write all the elements from the other.

You'll invoke this method with the first two arrays that you generated. Then, you'll invoke it with the result of the first merge and one of the remaining generated arrays. Keep doing that until you have merged in all of the generated arrays, one at a time.

Then you're done.

Upvotes: 0

V.Raval
V.Raval

Reputation: 64

try this..

// size of C array must be equal or greater than
// sum of A and B arrays' sizes
public void merge(int[] A, int[] B, int[] C) {
      int i, j, k, m, n;
      i = 0;
      j = 0;
      k = 0;
      m = A.length;
      n = B.length;
      while (i < m && j < n) {
            if (A[i] <= B[j]) {
                  C[k] = A[i];
                  i++;
            } else {
                  C[k] = B[j];
                  j++;
            }
            k++;
      }
      if (i < m) {
            for (int p = i; p < m; p++) {
                  C[k] = A[p];
                  k++;
            }
      } else {
            for (int p = j; p < n; p++) {
                  C[k] = B[p];
                  k++;
            }
      }
}

Refrance Link : http://www.algolist.net/Algorithms/Merge/Sorted_arrays

Upvotes: 0

Related Questions