Hello, I am bugfree Assistant. Feel free to ask me for any question related to this problem
To merge two pre-sorted arrays into a single sorted array, we can utilize a technique that efficiently combines elements from both arrays in a sorted manner. The primary approach here is to use a two-pointer technique, which allows us to traverse both arrays simultaneously and append the smaller element to the resulting array. This method ensures that the final array is sorted and can be achieved in linear time, O(n+m), where n and m are the lengths of the two input arrays.
Initialize Pointers: Start by initializing two pointers, i
and j
, to zero. These pointers will help us keep track of the current position in each of the input arrays.
Create Result Array: Create a new array, arr_3
, which will store the merged and sorted elements from both input arrays.
Iterate Through Arrays:
while
loop to iterate through both arrays as long as neither pointer has reached the end of its respective array.i
and j
in arr_1
and arr_2
, respectively.arr_3
and move the corresponding pointer forward by one.Handle Remaining Elements:
while
loops to append any remaining elements to arr_3
.Return Result: Once both arrays have been completely traversed and merged, return the arr_3
as the final sorted array.
def merge_arrays(arr_1, arr_2):
arr_3 = []
i = 0
j = 0
x = len(arr_1)
y = len(arr_2)
# Traverse both arrays
while i < x and j < y:
if arr_1[i] < arr_2[j]:
arr_3.append(arr_1[i])
i += 1
else:
arr_3.append(arr_2[j])
j += 1
# Append remaining elements of arr_1
while i < x:
arr_3.append(arr_1[i])
i += 1
# Append remaining elements of arr_2
while j < y:
arr_3.append(arr_2[j])
j += 1
return arr_3
# Example Usage
arr_1 = [1, 2, 9, 11]
arr_2 = [3, 4, 6, 8]
print(merge_arrays(arr_1, arr_2)) # Output: [1, 2, 3, 4, 6, 8, 9, 11]
arr_1
and m is the length of arr_2
. This is because each element from both arrays is processed exactly once.arr_3
.