Searching Mergesort algorithm using Java's standard LinkedList

Question

I want to sort a LinkedList in Java using a Mergesort algorithm.
I've researched in the internet for a solution but the algorithms I found sort either an Array or a self declared LinkedList. As I mentioned earlier I need an algorithm which sorts the standard java LinkedList (java.util.LinkedList).
In addition to my research I tried to implement one myself but I'm not capable of doing so. I was able to create the 'divide' part but I couldn't program the 'conquer' (merge in the sorted order) part.
This is my code:

private void mergeSort(LinkedList<Integer> list) {
        if (list.size() < 2){
            return;
        }
        int middleindex  = list.size()/2;
        LinkedList<Integer> [] listArr = split(list, middleindex);

        LinkedList<Integer> leftList = listArr[0];
        mergeSort(leftList);

        LinkedList<Integer> rightList = listArr[1];
        mergeSort(rightList);

        sortedMerge(rightList, leftList, list);

    }

    private void sortedMerge(LinkedList<E> right, LinkedList<E> left, LinkedList<E> list){
        //sort and merge
    }


    @SuppressWarnings("unchecked") private static <T> LinkedList<T>[] split(LinkedList<T> list, int index) {
        LinkedList<T> left = new LinkedList<>();

        for (int i = 0; i < index; i++) {
            T t = list.removeFirst();
            left.addLast(t);
        }
        return new LinkedList[] {
                left, list
        };
    }

Can someone help me and create the 'sortedMerge()' method?

Answer 1

The Collections.sort() method sorts the LinkedList. It does so by copying the contents of LinkedList to an array, sorting the array, and copying the contents of array back to LinkedList. You can implement the same functionalities as the Collections.sort() method and use the merge sort algorithm to sort the array.

Below I have detailed my steps and correct code that sorts Java's standard LinkedList using Merge Sort algorithm.

Steps:

1. Create a LinkedList 'orginialList'
2. Convert 'originalList' to Integer array 'arr'
3. Convert 'arr' to int array 'intArray'
4. Sort 'intArray' using the merge sort algorithm
5. Convert sorted 'intArray' back to Integer array 'arr' (use for loop to change elements in 'arr')
6. Create a LinkedList 'newList'
7. Add elements of 'arr' to 'newList' (use Arrays.asList(arr))

     public static class CollectionsSort {
         public static void main(String[] args) {
               LinkedList<Integer> originalList = new LinkedList<>();
               originalList.add(3);
               originalList.add(2);
               originalList.add(1);

               Integer[] arr = list.toArray(new Integer[list.size()]);
               int[] intArray = new int[arr.length];
               for (int i = 0; i < intArray.length; i++) {
                   intArray[i] = arr[i].intValue();
               }
               mergesort(intArray);
               for (int i = 0; i < arr.length; i++) {
                   arr[i] = new Integer(intArray[i]); 
               }
               LinkedList<Integer> newList = new LinkedList(Arrays.asList(arr));
               Iterator it = newList.iterator();
               while(it.hasNext()) {
                  System.out.print((int)(it.next()) + " ");
               }
         }

         public static int[] mergesort(int[] arr) {
               int low = 0;
               int high = arr.length-1;
               mergesort(arr, low, high);
               return arr;
         }

         public static void mergesort(int[] arr, int low, int high) {
               if (low == high) {
                   return;
               } else {
                   int middle = low + (high-low)/2;
                   mergesort(arr, low, middle);
                   mergesort(arr, middle+1, high);
                   merge(arr, low, middle, high);
               }
         }

         public static void merge(int[] arr, int low, int mid, int high) {
               int[] left = new int[mid-low+2];
               for (int i = low; i <= mid; i++) {
                   left[i-low] = arr[i];
               }
               left[mid-low+1] = Integer.MAX_VALUE;
               int[] right = new int[high-mid+1];
               for(int i = mid+1; i <= high; i++) {
                   right[i-mid-1] = arr[i];
               }
               right[high-mid] = Integer.MAX_VALUE;
               int i = 0, j = 0;
               for(int k = low; k <= high; k++) {
                   if(left[i] <= right[j]) {
                      arr[k] = left[i];
                      i++;
                   } else {
                      arr[k] = right[j];
                      j++;
                   }
               }
         }
     }