Merge Sort Java

Question

This is the merge part of my solution. Method merge merges two already sorted lists. I feel the code I wrote isn't the best implementation. Please review the code and tell me where I can improve.

public static List<Integer> merge(List<Integer> tomerge1,List<Integer> tomerge2){
    int n = tomerge1.size();
    int m = tomerge2.size();
    List<Integer> result = new ArrayList();
    int i=0;
    int j=0;
    while(i<n){

        while(j<m && tomerge1.get(i)>tomerge2.get(j)){
                result.add(tomerge2.get(j));
                j++;
        }
        result.add(tomerge1.get(i));
        i++;
        try {
            tomerge1.get(i); // If all the elements of 1 are added to the 
                             // result and some elements of the 2nd remain, 
                             // this line will give IndexOutOfRange error.
        }catch (Exception e){
            while(j<m){
                result.add(tomerge2.get(j));
                j++;
            }
        }
    }
    return result;
}

Answer 1

Don't rely on exceptions to cover certain program logic

    try {
        tomerge1.get(i); // If all the elements of 1 are added to the 
                         // result and some elements of the 2nd remain, 
                         // this line will give IndexOutOfRange error.
    }catch (Exception e){
        while(j<m){
            result.add(tomerge2.get(j));
            j++;
        }
    }

• You rely on catching a IndexOutOfRange error. Specify that in the catch statement:

  catch (IndexOutOfRange e){ // ...
  

  if you do so

• You should generally not use exceptions to cover some certain logical control flow. Rather use regular conditional statements, e.g.

  if(tomerge1.size() >= i) {
      while(j<m){
          result.add(tomerge2.get(j));
          j++;
      }
  }
  

Answer 2

public static List<Integer> merge(List<Integer> tomerge1,List<Integer> tomerge2){
  int n = tomerge1.size();
  int m = tomerge2.size();
  List<Integer> result = new ArrayList();
  int i=0;
  int j=0;
  while(i<n){

The loop below adds all elements of tomerge2 as long as they're smaller than the current element of tomerge1. So far so good.

      while(j<m && tomerge1.get(i)>tomerge2.get(j)){
              result.add(tomerge2.get(j));
              j++;
      }

Here you add only a single element of tomerge1.

      result.add(tomerge1.get(i));
      i++;

You increased i and instead of checking if i is now out of range like this:

if(i >= n) 

... you just try to access the next element without even looking at the result. Not good. You don't even need to do this check though, instead just let the outer while loop exit. Then after that loop, check if there any remainign elements of tomerge2 and only execute this part:

          while(j<m){
              result.add(tomerge2.get(j));
              j++;
          }

Answer 3

About Exception, if you want to use Exception for business logic you can do it without any affection to performance. Since java 7 we have https://docs.oracle.com/javase/7/docs/api/java/lang/Exception.html#Exception(java.lang.String,%20java.lang.Throwable,%20boolean,%20boolean)

Use constructor with 4 parameters

new Exception("message", null, false, false)