Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should…

One Answer on this Question

1. To merge the two sorted halves of an integer array in place, you can use a modified version of the merge step in the merge sort algorithm. The idea is to start merging the two halves from the end of the array, so that there is no need for additional space.

   Here’s a C++ implementation of the function:

   cpp
   Copy code
   #include

   void mergeSortedHalves(int arr[], int size) {
   int i = (size / 2) – 1; // Last index of the first half
   int j = size – 1; // Last index of the array
   int k = size – 1; // Last index of the merged array

   while (i >= 0 && j >= size / 2) {
   if (arr[i] >= arr[j]) {
   arr[k] = arr[i];
   i–;
   } else {
   arr[k] = arr[j];
   j–;
   }
   k–;
   }

   // Copy any remaining elements from the first half to the merged array
   while (i >= 0) {
   arr[k] = arr[i];
   i–;
   k–;
   }

   // The second half is already in its correct position

   // Print the merged array
   for (int m = 0; m < size; m++) {
   std::cout << arr[m] << " ";
   }
   std::cout << std::endl;
   }

   int main() {
   int arr[] = {1, 3, 6, 8, -5, -2, 3, 8};
   int size = sizeof(arr) / sizeof(arr[0]);

   mergeSortedHalves(arr, size);

   return 0;
   }
   In this implementation, the mergeSortedHalves function takes an integer array arr and its size size as input. It assumes that the first half and second half of the array are already sorted.

   The function initializes three pointers: i pointing to the last element of the first half, j pointing to the last element of the array, and k pointing to the last position of the merged array. It starts comparing elements from both halves and places the larger element at the position k in the merged array. The corresponding pointer is then decremented, and k is also decremented.

   After merging the elements from the first half, the function copies any remaining elements from the first half to the merged array.

   Finally, it prints the merged array.

   Output:

   diff
   Copy code
   -5 -2 1 3 3 6 8 8

   Reply