Merge elements in an array I have written two different codes for merging (merging with costs) and I want to know if I can make optimizations to run faster.

merge1:

 private static long merge(List&lt;Integer&gt; array, int[] res, int start, int mid, int end) {

        int i = start; // index of left subarray
        int j = mid; // index of right subarray
        int k = start; //index of mid

        long inversions = 0;

        for (int r = start; r &lt;= end; r++) {

            if ((j &gt; end) || (i &lt; mid &amp;&amp; array.get(i) &lt;= array.get(j))) {
                res[r] = array.get(i);
                i++;
            } else {

                if (i &lt; mid) {

                    if (array.get(i) - array.get(j) &gt; 1) {

                        inversions += 3 * (mid - i);
                    } else {
                        int s;
                        s = MostRightSmallestElement.search(array, i, mid - 1);
                        inversions += 2 * (s - i + 1);
                        inversions += 3 * (mid - (s + 1));
                    }

                }
                res[r] = array.get(j);
                j++;

            }
        }



       //Copy the remaining elements of left subarray  (if there are any) to res
        while (i &lt;= mid - 1) {
            res[k++] = array.get(i++);
        }

        //Copy the remaining elements of right subarray  (if there are any) to res
        while (j &lt;= end) {
            res[k++] = array.get(j++);
        }

        //Copy back the merged elements to original array
        for (i = start; i &lt;= end; i++) {
            array.set(i, res[i]);
        }

        return inversions;

    }


merge2:

private static long merge(List&lt;Integer&gt; array, int[] res, int start, int mid, int end) {

        int i = start; // index of left subarray
        int j = mid; // index of right subarray
        int k = start; //index of mid

        long inversions = 0;


        while( ( i &lt;mid) &amp;&amp; (j &lt;= end )) {

            if( array.get(i) &lt;=  array.get(j)){
                res[k++] = array.get(i++);
            }
            else {

                if (i != mid) {

                    if (array.get(i) - array.get(j) &gt; 1) {

                        inversions =  inversions + 3 * (mid - i);

                    } else {
                          int s;
                        s = MostRightSmallestElement.search(array, i, mid - 1);
                        inversions =  inversions +  2 * (s - i + 1);
                        inversions =  inversions +  3 * (mid - (s + 1));
                    }
          }
                res[k++] = array.get(j++);

        }
        }

       //Copy the remaining elements of left subarray  (if there are any) to res
        while (i &lt;= mid - 1) {
            res[k++] = array.get(i++);
        }

        //Copy the remaining elements of right subarray  (if there are any) to res
        while (j &lt;= end) {
            res[k++] = array.get(j++);
        }

        //Copy back the merged elements to original array
        for (i = start; i &lt;= end; i++) {
            array.set(i, res[i]);
        }

        return inversions;

    }


Any ideas how I can optimize the code? I count the inversions but the general
idea of merging is the same.
comparative-review:
In both variants, both "traversing indices" get compared to their (respective upper) limit in each traversal of the "proper merge loop".
While "the copy2res-loops" should never execute in merge1, the "res-index" gets compared to its limit right from the start.
In merge2, the "proper merge loop" isn't traversed as often.
Exactly one of the copy2res-loops should be traversed for the same total.

remarks:  


merge() isn't doc-commented.
the comments for start&amp;mid might as well be @params,
index of mid looks off,
all three may be final.  
Both subarrays include their start - excluding end would be consistent.  
I don't get the inversion counting - lack of documentation doesn't help.


Speed-up:  


beware memory hierarchy effects
old school complexity analysis assumes uniform memory access time - far from what I'd want to pay and wait for.
don't copy back and fro. Use the auxiliary sequence as the/one source for the next pass.
don't convert between Integer and int time and again.  
when using Lists, avoid relying on the "random accessors" to be fast
(implementing RandomAccess is a hint - read backwards, its doc recommends to "always")
use ListIterators to iterate Lists  (note how they (optionally) support set(newValue))
don't time-consumingly ponder/implement variants unless you


established it matters
fixed a measure for good enough

converting to arrays and never looking back (with the possible exception of a terminating conversion/copy back) is an option promising sequential storage and allowing bulk operations. With Lists, operations on sublists may be more efficient.  
Most JREs allow a peek at their implementation (have a look at java.util.Arrays, too).