Generic MergeSort with Permutation Array

Question

I have code for a MergeSort of generic arrays. The only problem is, that I want the output to be with the index instead of the actual int, float or whatever. Do you guys have any idea on how to do that? Here is the code I have so far:

class MergeSortGeneric<T extends Comparable<? super T>> {
public static void main(String[] args)
    {
    // example using Strings
    String[] arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", 
 "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", 
"Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
    MergeSortGeneric<String> stringSorter   = new MergeSortGeneric<>();
    stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);
    System.out.println(java.util.Arrays.toString(arrayOfStrings));

    // example using Doubles
    Double[] arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 
0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
    MergeSortGeneric<Double> doubleSorter   = new MergeSortGeneric<>();
    doubleSorter.mergeSort(arrayOfDoubles, 0, arrayOfDoubles.length - 1);
    System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    // main function that sorts array[start..end] using merge()
    void mergeSort(T[] array, int start, int end)
    {
    // base case
    if (start < end)
    {
       // find the middle point
       int middle = (start + end) / 2;

       mergeSort(array, start, middle); // sort first half
       mergeSort(array, middle + 1, end);  // sort second half

      // merge the sorted halves
      merge(array, start, middle, end);
    }
    }

    // merges two subarrays of array[].
    void merge(T[] array, int start, int middle, int end)
    {
    T[] leftArray  = (T[]) new Comparable[middle - start + 1];
    T[] rightArray = (T[]) new Comparable[end - middle];

    // fill in left array
    for (int i = 0; i < leftArray.length; ++i)
    leftArray[i] = array[start + i];

    // fill in right array
    for (int i = 0; i < rightArray.length; ++i)
    rightArray[i] = array[middle + 1 + i];

    /* Merge the temp arrays */

    // initial indexes of first and second subarrays
    int leftIndex = 0, rightIndex = 0;

    // the index we will start at when adding the subarrays back into the main array
    int currentIndex = start;

    // compare each index of the subarrays adding the lowest value to the currentIndex
    while (leftIndex < leftArray.length && rightIndex < rightArray.length)
    {
    if (leftArray[leftIndex].compareTo(rightArray[rightIndex]) <= 0)
    {
    array[currentIndex] = leftArray[leftIndex];
    leftIndex++;
    }
    else
    {
    array[currentIndex] = rightArray[rightIndex];
    rightIndex++;
    }
    currentIndex++;
    }

    // copy remaining elements of leftArray[] if any
    while (leftIndex < leftArray.length) array[currentIndex++] = leftArray[leftIndex++];

    // copy remaining elements of rightArray[] if any
    while (rightIndex < rightArray.length) array[currentIndex++] = rightArray[rightIndex++];
    }
}

thank you guys for any tips. Thats the task by the way: Implement the Merge-Sort algorithm. The algorithm sorts a java.util.list of any elements. Therefore the class must be generic. For sorting it gets a matching comparator.

var data = Arrays.asList(23, 42, 11, 1, 12);
var mergeSort = new MergeSort<Integer>();
mergeSort.setup(data, (i1, i2) -> i1 - i2);

However, the element positions in the input list are not changed. Instead, the specifies the sorting by a permutation array. The array has as many in-elements as the input data list has elements. Each τ element specifies the index of the corresponding input element after sorting. Also internally you use only permutation arrays and no further lists of input elements.

Answer 1

you can create a class like below (note it is pseudo code)

import java.util.Arrays;

public class SomeClass {

    public static void main(String[] args) {
        double[] doubleArray = new double[] {2.3, 3.4, 1.2, 0.3, 4.3};
        ObjectWithIndex[] objectWithIndexAr = new ObjectWithIndex[doubleArray.length];
        for (int i = 0; i < doubleArray.length; i++) {
            objectWithIndexAr[i] = new ObjectWithIndex(i, doubleArray[i]);
        }

        Arrays.sort(objectWithIndexAr);

        for ( ObjectWithIndex obj : objectWithIndexAr) {
            System.out.println("index: " + obj.index + " value: " + obj.actualObject);
        }
    }
}

class ObjectWithIndex implements Comparable<ObjectWithIndex> {
    int index;
    Comparable actualObject;

    public ObjectWithIndex(int index, Comparable object) {
        this.index = index;
        this.actualObject = object;
    }

    @Override
    public int compareTo(ObjectWithIndex o) {
        return this.actualObject.compareTo(o.actualObject);
    }
}

you can create array of this object using your input array of Double, Integer (whatever implements Comparable) and sort the new array of ObjectWithIndex.

once sorted, you can print the index (which will have original index from your input)

Answer 2

You can use a lambda compare, if the indexes are Integer types as opposed to native ints. Only the array of indices needs to be Integer type, the array of values can be primitive type.

package x;
import java.util.Arrays;
public class x {
    public static void main(String[] args) {
        int[] A = {3, 1, 2, 0};
        Integer[] I = {0, 1, 2, 3};
        Arrays.sort(I, (i, j) -> A[i]-A[j]);
        for (Integer i : I) {
            System.out.println(A[i]);
        }
    }
}

Answer 3

The easiest way without modifying the merge algorithm you be:

1. Create a copy of the arrays to be sorted;
2. Sort the arrays;
3. Compare the copy and the sorted array and figure it out the index.

For example:

String[] arrayOfStrings = {...};
List<String> copyArrayOfStrings = Arrays.stream(arrayOfStrings).collect(Collectors.toList());

...
stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);
...

List<Integer> index = Arrays.stream(arrayOfStrings).map(copyArrayOfStrings::indexOf).collect(Collectors.toList());
System.out.println(java.util.Arrays.toString(index.toArray()));

If for some strange reason you can only use arrays, and basic operators, the aforementioned logic still holds true:

the copy:

 String[] copyArrayOfStrings = new String[arrayOfStrings.length];
    for(int i  = 0; i < arrayOfStrings.length; i++){
       copyArrayOfStrings[i] = arrayOfStrings[i];
    } 

the sorting:

    stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);

getting the indexes:

    Integer[] index = new Integer[copyArrayOfStrings.length];
    int index_pos = 0;
    for(String s : arrayOfStrings) {
        for (int i = 0; i < copyArrayOfStrings.length; i++) {
            if(copyArrayOfStrings[i].equals(s)){
                index[index_pos++] = i;
                break;
            }
        }
    }

    System.out.println(java.util.Arrays.toString(index));