Java solves a special array merge problem

  • 2020-04-01 03:22:03
  • OfStack

Given two sorted arrays A and B, where the end of A has enough space for B, write A method to merge B into A and sort it.

Once you get this, the immediate idea is to compare the elements in A and B and insert the array in order until you have traversed all the elements in A and B. But there is A downside to doing this: if the element is inserted at the front of the array A, the original array must be moved back. This adds to the overhead. But there's another way to insert elements into the end of array A. So that we don't have elements moving around! The code is as follows:
       
 
      public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
  int indexA = lastA - 1; 
  int indexB = lastB - 1;
  int mergeIndex = lastA + lastB - 1; 
  while (indexA >= 0 && indexB >= 0) {
   if (a[indexA] > b[indexB]) {
    a[mergeIndex] = a[indexA];
    mergeIndex --;
    indexA --;
   } else {
    a[mergeIndex] = b[indexB];
    mergeIndex --;
    indexB --;
   }
  }

  while (indexB >= 0) {
   a[mergeIndex] = b[indexB];
   mergeIndex --;
   indexB --;
  }
 }

Related articles: