Merge Sorting In Place

Question

I am working on a Merge Sort method which sorts elements in-place without allocating extra memory. However, it isn't working as of now and I was wondering if anyone could help me, as I understand it is a relatively simple operation. Thank you in advance.

My merge sort method:

      RegisterClass[] runMergeSort()
  {
     RegisterClass[] mergeSorted = new RegisterClass[capacity];
     
     for (int counter = 0; counter < size; counter++)
        {
           mergeSorted[counter] = registerArray[counter];
        }
     
     runMergeSortHelper(mergeSorted, 0, size - 1);
     
     return mergeSorted;
  }

My helper method, which uses recursion:

      private void runMergeSortHelper(RegisterClass[] workingArray,
                                  int lowIndex,
                                  int highIndex)
  {
     int midIndex = (lowIndex + highIndex) / 2;
     
     if (lowIndex < highIndex)
        {
           
           runMergeSortHelper(workingArray, lowIndex, midIndex);
           runMergeSortHelper(workingArray, midIndex+1, highIndex);
                          
           runMerge(workingArray, lowIndex, midIndex, highIndex);
        }
              

  }

And finally, my Merge method, which SHOULD be putting everything into order, however, it only does this partially.

      private void runMerge(RegisterClass[] workingArray,
                        int lowIndex,
                        int midIndex,
                        int highIndex)
  {
     int counterJay = midIndex;
     int counterAye = lowIndex;
     int counterKay = lowIndex - 1;
              
     while (counterAye < midIndex && counterJay <= highIndex)
        {
           counterKay++;
           
           if (workingArray[counterAye].compareTo(workingArray[counterJay]) <= -1)
              {
                 counterAye++;
              }
           
           else
              {
                 swapValues(workingArray, counterAye, counterJay);
                 counterJay++;
                 counterAye++;
              }
           
        }
     
     while (counterAye < midIndex)
        {
           counterKay++;
           swapValues(workingArray, counterAye, counterKay);
           counterAye++;
        }
     
     while (counterJay <= highIndex)
        {
           counterKay++;
           swapValues(workingArray, counterJay, counterKay);
           counterJay++;
        }
  }

Any advice at all would much be appreciated. I've looked online but nothing seems to help. Please do not refer me to a solution which is NOT an in-place solution.

Answer 1

Swapping isn't going to work with the logic used by the merge function. When a swap occurs, the element that is swapped from the left side to the right side is now out of order, and will be less than (or equal to) all of the remaining elements on the left side.

Whenever an element on the right side is found to be less than an element on the left side, a right rotate of that part of the array is needed to put the right side element into place.

---

Without resorting to a more complicated implementation, a small optimization can be made by scanning the right side for k = number of leading elements less than the current element on the left side, then do a rotate right by k elements. For random data, this won't help much, but for reverse sorted data, it would help quite a bit.