Mergesort of multi-dimensional array in Java

Question

I have a function which should sort a 2D String array according to a 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][10],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 for each element.

Answer 1

This is a great question because it brings up the complicated problem of sorting a table with columns of unlike types. Later versions of Java implement new sorting tools you can use. Here's my solution to your problem using JDK 1.8 (Java 8). It's printing only fields 0,1,7 although you can easily add in the rest of the fields.

First class file:

package intquestions;
import java.util.ArrayList;
import java.util.Collections;
import static java.lang.System.out;
import intquestions.StaffComparator;

public class SortDataList   {
    public static void main(String[] args) {
        runit();     }    

    public static void runit() {        
        Object[] list1 = {"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"    };
        Object[] list2 = {"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"};
        Object[] list3 = {"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"};
        Object[] list4 = {"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"};

        ArrayList<DataList> mList=new java.util.ArrayList<DataList>(); 
        mList.add(new DataList(list1));
        mList.add(new DataList(list2));
        mList.add(new DataList(list3));
        mList.add(new DataList(list4));
        String sep = "  |   " ;
        out.println("BEFORE SORTING - ONLY PRINTING FIELDS 1,2,8 (0,1,7) ---------------------- :   "  );
        out.println(mList.get(0).s.toString() +sep+ mList.get(0).f.toString() +sep+ mList.get(0).eighth.toString());
        out.println(mList.get(1).s.toString() +sep+ mList.get(1).f.toString() +sep+ mList.get(1).eighth.toString());
        out.println(mList.get(2).s.toString() +sep+ mList.get(2).f.toString() +sep+ mList.get(2).eighth.toString());
        out.println(mList.get(3).s.toString() +sep+ mList.get(3).f.toString() +sep+ mList.get(3).eighth.toString());

        StaffComparator myComparator = new StaffComparator();

        try {   Collections.sort(mList, myComparator);  
        } catch (Exception e) {  out.println(e); }

        out.println("\nDONE SORTING - ONLY PRINTING FIELDS 1,2,8 (0,1,7)  ----------------------- :   "  );
        out.println(mList.get(0).s.toString() +sep+ mList.get(0).f.toString() +sep+ mList.get(0).eighth.toString());
        out.println(mList.get(1).s.toString() +sep+ mList.get(1).f.toString() +sep+ mList.get(1).eighth.toString());
        out.println(mList.get(2).s.toString() +sep+ mList.get(2).f.toString() +sep+ mList.get(2).eighth.toString());
        out.println(mList.get(3).s.toString() +sep+ mList.get(3).f.toString() +sep+ mList.get(3).eighth.toString());
    }
}    

class DataList extends DataListAbstract {
    public DataList(Object[] myObj) {
        super(myObj);     }

    public Integer getEighth(DataList locVarDataList) {
        return  locVarDataList.eighth; }

    @Override
    public int compareTo(DataListAbstract o) {
        return 0;     }
}

abstract class DataListAbstract implements Comparable<DataListAbstract> {
    String f;  // first
    String s; //second
    Integer eighth;
    DataListAbstract(Object[] myo) {
        this.eighth =  (Integer)myo[7]; 
        this.f =  (String)myo[0]; 
        this.s =  (String)myo[1]; 
    }
}

Second class:

package intquestions;
import java.util.Comparator;

public class StaffComparator implements Comparator<DataList> {
    public int compare(DataList c1, DataList c2) {
        Integer firstInt = c1.getEighth(c1);
        Integer secondInt = c2.getEighth(c2);
        return firstInt.compareTo(secondInt);
    }
}

Output:

BEFORE SORTING - ONLY PRINTING FIELDS 1,2,8 (0,1,7) ---------------------- :   
192.168.1.101  |   192.168.1.101-67.212.184.66-2156-80-6  |   2328040
192.168.1.101  |   192.168.1.101-67.212.184.66-2159-80-6  |   2328006
192.168.2.106  |   192.168.2.106-192.168.2.113-3709-139-6  |   7917
192.168.5.122  |   192.168.5.122-64.12.90.98-59707-25-6  |   113992

DONE SORTING - ONLY PRINTING FIELDS 1,2,8 (0,1,7)  ----------------------- :   
192.168.2.106  |   192.168.2.106-192.168.2.113-3709-139-6  |   7917
192.168.5.122  |   192.168.5.122-64.12.90.98-59707-25-6  |   113992
192.168.1.101  |   192.168.1.101-67.212.184.66-2159-80-6  |   2328006
192.168.1.101  |   192.168.1.101-67.212.184.66-2156-80-6  |   2328040