Merge Sorted Array

class Solution {
public:
    void mergeSortedArrays(vector<int>& first, int size1, vector<int>& second, int size2) {
        int index1 = size1 - 1;
        int index2 = size2 - 1;
        for (int indexMerged = size1 + size2 - 1; indexMerged >= 0; indexMerged--) {
            if (index2 < 0) {
                break;
            }
            if (index1 >= 0 && first[index1] > second[index2]) {
                first[indexMerged] = first[index1--];
            } else {
                first[indexMerged] = second[index2--];
            }
        }
    }
};

The provided C++ code defines a method mergeSortedArrays that merges two presorted integer vectors into one of the vectors, specifically into the first vector. The function takes two vectors, first and second, and their respective sizes, size1 and size2.

• The code initializes two pointers, index1 and index2, at the end of the non-empty parts of both first and second vectors respectively.
• A third pointer, indexMerged, is also initialized at the last position of the combined array size.
• It uses a for loop to iterate backwards through the first vector's extended size (which includes room for the second vector's elements).
• Inside the loop, the elements from first and second are compared. The larger element is placed into the current position of indexMerged in the first vector.
• The loop terminates early if all elements from the second vector have been placed into the first.

This method ensures that the merged array is sorted without needing additional storage space, effectively integrating the two arrays into a single sorted array in a space-efficient manner. This solution is particularly efficient for scenarios where extra space utilization needs to be minimized.

class Solution {
    public void mergeSortedArrays(int[] array1, int len1, int[] array2, int len2) {
        int index1 = len1 - 1;
        int index2 = len2 - 1;

        for (int i = len1 + len2 - 1; i >= 0; i--) {
            if (index2 < 0) {
                break;
            }
            if (index1 >= 0 && array1[index1] > array2[index2]) {
                array1[i] = array1[index1--];
            } else {
                array1[i] = array2[index2--];
            }
        }
    }
}

The provided Java solution tackles the problem of merging two sorted arrays into one sorted array. The approach modifies the first array (array1) to include all elements from both arrays, as it assumes that array1 has enough space to hold elements from both array1 and array2.

Here's how the merging process is executed:

• Initialize two pointers, index1 and index2, to point to the ends of array1 and array2 respectively.
• Use a loop that goes backwards through array1, starting from its last position, which is the sum of len1 and len2 minus one, and decrements down to zero.
• In each iteration of the loop:
  • If index2 is less than zero, end the loop, as it means all elements from array2 have been placed.
  • Compare the current elements pointed by index1 and index2 of array1 and array2 respectively.
  • Place the larger element at the current position i in array1 and decrement the respective index (index1 or index2).

This approach ensures that the larger elements are placed at the end of array1 first, making efficient use of space while preserving the sorted order. This solution is efficient and executes in linear time relative to the total number of elements, or O(n + m), where n is the number of elements in array1 and m is the number of elements in array2.

var mergeArrays = function (array1, len1, array2, len2) {
    let index1 = len1 - 1;
    let index2 = len2 - 1;
    for (let position = len1 + len2 - 1; position >= 0; position--) {
        if (index2 < 0) {
            break;
        }
        if (index1 >= 0 && array1[index1] > array2[index2]) {
            array1[position] = array1[index1--];
        } else {
            array1[position] = array2[index2--];
        }
    }
};

Merge two sorted arrays in-place in a predefined space within the first array. The function mergeArrays efficiently tackles this with the following steps:

1. Initialize two pointers index1 and index2 to point to the end of the actual elements in array1 and array2, respectively.
2. Begin a reverse iteration from the total length of both arrays combined.
3. Compare elements from the end of both arrays:
   • If the current element in array1 is larger, place it in the current position and decrement the index1.
   • Otherwise, place the element from array2 and decrement index2.
4. Exit earlier if array2 is exhaustively merged, indicated by index2 being less than zero.

This function ensures optimal integration of two arrays by filling the first array from the end, thereby avoiding the overhead of moving unmerged elements with each insertion.

class Solution:
    def combine(self, first_list: List[int], len1: int, second_list: List[int], len2: int) -> None:
        # Initialize pointers for the merge process
        first_ptr = len1 - 1
        second_ptr = len2 - 1

        # Start from the end of the first list and fill backwards
        for idx in range(len1 + len2 - 1, -1, -1):
            if second_ptr < 0:
                break
            if first_ptr >= 0 and first_list[first_ptr] > second_list[second_ptr]:
                first_list[idx] = first_list[first_ptr]
                first_ptr -= 1
            else:
                first_list[idx] = second_list[second_ptr]
                second_ptr -= 1

The provided Python code defines a method to merge two pre-sorted integer arrays. This method, named combine, modifies the first array first_list in place by integrating elements from second_list, resulting in a single, fully merged and sorted array.

• Memory Efficiency: The merging happens in-place on the first_list utilizing the extra space at its end, which ensures that no additional storage is needed.

• Merging Logic: The solution uses three pointers:

  • first_ptr starts at the end of the actual elements in first_list (ignoring the extra space).
  • second_ptr starts at the end of second_list.
  • idx is used for setting the next value in first_list starting from the end towards the beginning.

• Process Details:

  • The function fills first_list by comparing values from the end of both first_list and second_list, copying the larger value into the current position pointed by idx.
  • Decrement the pointers (first_ptr or second_ptr) accordingly.
  • The loop stops when all elements of second_list have been merged, assuming there's enough space in first_list.

Ensure to have the appropriate length setup (i.e., both len1 and the reserve space for second_list included in first_list) before calling this function to avoid errors. The function is particularly optimal when you need to integrate two lists without additional memory overhead, typical in scenarios like merging logs, event streams, or sorted data from different sources directly into a designated buffer space.