Mergesort split into 2 arrays

Question

I'm trying to do an assignment, but I can't get this mergesort right. We basically have to make a new version of merge sort. First receiving the original array to sort, then we have to split it into 2 subarrays and then merge them back together on another method.

I CAN'T CHANGE how the methods are created, no changing what the type of return or the parameters, I can only change the body of it.

This is my code so far. The instructions of each method are stated at the top of it. (It is in Spanish D:)

/**
     * SII i<=f: devuelve un array con los elementos del subarray 
     * v[i, f] ordenados Asc. 
     * 
     * @param v  Sus elementos implementan la interfaz Comparable
     * @param i  Extremo inferior del intervalo a ordenar
     * @param f  Extremo superior del intervalo a ordenar
     * @return T[], el array resultante de ordenacion de v[i, f]
     */
    private static <T extends Comparable<T>> T[] mergeSort2(T[] v,
                                                             int i, int f) {
        T[] resultado = (T[]) new Comparable[f-i+1];                                                        
        if (i < f) {
            int m = (i + f) / 2;
            T[] v1 = Arrays.copyOfRange(v, i, m);
            T[] v2 = Arrays.copyOfRange(v, m, f);
            v1 = mergeSort2(v, i, m);
            v2 = mergeSort2(v, m + 1, f);
            resultado = merge2(v1, v2);
        }
        return resultado;
    }        
    
    /**
     * Devuelve el array mezcla de v1 y v2, dos arrays ordenados Asc.
     * 
     * @param v1  Sus elementos implementan la interfaz Comparable
     * @param v2  Sus elementos implementan la interfaz Comparable
     * @return T[], el array resultante de la fusion de v1 y v2
     */
    
    private static <T extends Comparable<T>> T[] merge2(T[] v1, T[] v2) {
        T[] aux = (T[]) new Comparable[v1.length + v2.length];
        int i = 0, j = 0, k = 0;
        while (i < v1.length && j < v2.length)  
           aux[k++] = v1[i].compareTo(v2[j]) < 0 ? v1[i++] :  v2[j++];
    
        while (i < v1.length)  
            aux[k++] = v1[i++];
    
        while (j < v2.length)    
            aux[k++] = v2[j++];
    
        return aux;
    }

I've been trying this all day. Please help!

Answer 1

Since the functions return arrays, you don't need to create them. Note that mergeSort returns a Comparable, but the returned array will be of the same type as the input array. The calling parameters are indexes to first and last elements (it is more common to use first and ending (last+1) indexes).

import java.util.Arrays;
import java.util.Random;
// ...

    private static <T extends Comparable<T>> T[] mergeSort2(T[] v,
                                                             int i, int f) {
        if (i < f) {
            int m = (i + f) / 2;
            T[] v1 = mergeSort2(v, i, m);
            T[] v2 = mergeSort2(v, m + 1, f);
            return merge2(v1, v2);
        }
        return Arrays.copyOfRange(v, i, f);
    }        
    
    private static <T extends Comparable<T>> T[] merge2(T[] v1, T[] v2) {
        T[] aux = (T[]) new Comparable[v1.length + v2.length];
        int i = 0, j = 0, k = 0;
        while (i < v1.length && j < v2.length)  
           aux[k++] = v1[i].compareTo(v2[j]) < 0 ? v1[i++] :  v2[j++];
        while (i < v1.length)  
            aux[k++] = v1[i++];
        while (j < v2.length)    
            aux[k++] = v2[j++];
        return aux;
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[1024*1024];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        Comparable[]b = mergeSort2(a, 0, a.length-1);
        end = System.currentTimeMillis();

        for(int i = 1; i < b.length; i++){
            if(b[i-1].compareTo(b[i]) > 0){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }