MergeSort in 2D Array Java

Question

I have function for which should sort 2D String array according to some feature index. Here is my 2D array of 4 elements (4 x 10).

String[][] testArr = {
                {"192.168.1.101-67.212.184.66-2156-80-6","192.168.1.101","2156","67.212.184.66","80","6","13/06/2010 06:01:11","2328040","2","0"}
               ,{"192.168.1.101-67.212.184.66-2159-80-6","192.168.1.101","2159","67.212.184.66","80","6","13/06/2010 06:01:11","2328006","2","0"}
               ,{"192.168.2.106-192.168.2.113-3709-139-6","192.168.2.106","3709","192.168.2.113","139","6","13/06/2010 06:01:16","7917","10","9"}
               ,{"192.168.5.122-64.12.90.98-59707-25-6","192.168.5.122","59707","64.12.90.98","25","6","13/06/2010 06:01:25","113992","6","3"}
                };

I want to sort these elements according to lets say their 7th index, which is (2328040,2328006,7917,113992) in each element respectively. Here is the function I wrote for it:

// ************MERGE SORT***************************
public static void mergeSort(String[][] arr,int featureIndex){
        mergeSort(arr,new String [arr.length][84],0,arr.length-1,featureIndex);

}
// MERGE SORT HELPER FUNCTION
public static void mergeSort(String[][] arr,String [][] temp,int leftStart,int rightEnd,int featureIndex){
        if(leftStart >= rightEnd){
            return;
        }
        int mid = (leftStart + rightEnd)/2;
        mergeSort(arr,temp,leftStart, mid,featureIndex);
        mergeSort(arr,temp,mid + 1, rightEnd,featureIndex);
        mergeHalves(arr,temp,leftStart,rightEnd,featureIndex);
}
// Merge 2 Halves
public static void mergeHalves(String[][] arr,String[][] temp,int leftStart,int rightEnd,int featureIndex){
        int leftEnd = (rightEnd + leftStart)/2;
        int rightStart = leftEnd + 1;
        int size = rightEnd - leftStart + 1;

        int left = leftStart;
        int right = rightStart;
        int index = leftStart;


        while(left <= leftEnd && right <= rightEnd){
            if(Double.parseDouble(arr[left][featureIndex]) <= Double.parseDouble(arr[right][featureIndex])){
                temp[index][featureIndex] = arr[left][featureIndex];
                left++;
            }else{
                temp[index][featureIndex] = arr[right][featureIndex];
                right++;
            }
                index++;
        }
        // Copy the arrays
        System.arraycopy(arr, left, temp, index, leftEnd - left + 1);
        System.arraycopy(arr, right, temp, index, rightEnd - right + 1);
        System.arraycopy(temp, leftStart, arr, leftStart, size);

}

When I run the program it prints out 7917 7917 7917 113992 respectively in each element. How can I fix this?

Answer 1

Your merge function has some problems, you could simplify the function to

public static void mergeHalves(String[][] array,
                               String[][] aux,
                               int start, int middle, 
                               int end, 
                               int index) {

    if (start >= end) return;

    int ls = start, le = middle, rs = middle + 1, re = end, size = end - start + 1;

    for (int i = 0; i < size; i++) {
        if (rs > re) {
            aux[i] = array[ls++];
        } else if (ls > le) {
            aux[i] = array[rs++];
        } else if (Double.parseDouble(array[ls][index]) 
                <= Double.parseDouble(array[rs][index])) {
            aux[i] = array[ls++];
        } else {
            aux[i] = array[rs++];
        }
    }

    System.arraycopy(aux, 0, array, start, size);

}

Using this approach (merge sort of a array of arrays), you would need to deal with the types in the array, because in this case you cannot use parseDouble the columns 0, 1, 3 and 6. You could use a Comparator of string Comparator<String> as variable in mergeHalves() replacing the comparation in the else if with comparator.compare(array[ls][index], array[rs][index]) <= 0. Then defining and passing the comparator acording to the type of data.