Write a Python function to merge two sorted arrays without using built-in sort.
- User
Write a Python function to merge two sorted arrays without using built-in sort.
Assistant
Here's a Python function that merges two sorted arrays without using built-in sort:
def merge_sorted_arrays(arr1, arr2): """ Merge two sorted arrays into a single sorted array. Args: arr1: First sorted array arr2: Second sorted array Returns: A new sorted array containing all elements from both input arrays """ merged = [] i = 0 # pointer for arr1 j = 0 # pointer for arr2 # Compare elements from both arrays and add the smaller one while i < len(arr1) and j < len(arr2): if arr1[i] <= arr2[j]: merged.append(arr1[i]) i += 1 else: merged.append(arr2[j]) j += 1 # Add remaining elements from arr1 (if any) while i < len(arr1): merged.append(arr1[i]) i += 1 # Add remaining elements from arr2 (if any) while j < len(arr2): merged.append(arr2[j]) j += 1 return merged # Example usage: arr1 = [1, 3, 5, 7, 9] arr2 = [2, 4, 6, 8, 10] result = merge_sorted_arrays(arr1, arr2) print(result) # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # Another example with arrays of different sizes: arr3 = [1, 5, 8] arr4 = [2, 3, 4, 6, 7, 9, 10] result2 = merge_sorted_arrays(arr3, arr4) print(result2) # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]The algorithm works by:
- Using two pointers (i and j) to track positions in each array
- Comparing elements at the current positions and adding the smaller one to the result
- Moving the pointer forward in the array from which we took the element
- After one array is exhausted, appending all remaining elements from the other array
Time complexity: O(n + m) where n and m are the lengths of the input arrays Space complexity: O(n + m) for the merged array
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.