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;
}

• πάντα ῥεῖ: Your exception handling code looks a bit weird for me. At least it would be worth to put some comments how you actually recover arbitrary exceptions there. Exceptions shouldn't be abused to cover certain logical control flow in your code.
• sudo_dudo: I added comment to the code where I explained the logic. Is it wrong practice to use exceptions like I used?
• john16384: Yes, it is bad practice to use exceptions in this way. Exceptions are expensive to throw (they create a stacktrace among other things) and since this is a sort algorithm, I suppose speed is an important consideration.
• sudo_dudo: @john16384 that seems pretty good reason to not use them like I did. I will make the necessary changes.
• πάντα ῥεῖ: @sudo_dudo Please don't edit your code in such a drastical way it will invalidate existing answers.

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++;
   }
  }
  

• πάντα ῥεῖ: @sudo_dudo And I rolled that back for reasons.

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)