Given an array of size N, implement Merge sort.Input FormatThe first line of input contains an integer N - the size of an array. The second line contains the elements of the array.Output FormatFor each merge call of Merge Sort, print the array elements.Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput65 1 3 15 10 4Output1 5 3 15 10 4 1 3 5 15 10 4 1 3 5 10 15 4 1 3 5 4 10 15 1 3 4 5 10 15
Question
Given an array of size N, implement Merge sort.Input FormatThe first line of input contains an integer N - the size of an array. The second line contains the elements of the array.Output FormatFor each merge call of Merge Sort, print the array elements.Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput65 1 3 15 10 4Output1 5 3 15 10 4 1 3 5 15 10 4 1 3 5 10 15 4 1 3 5 4 10 15 1 3 4 5 10 15
Solution 1
Here is a Python implementation of Merge Sort:
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
Solution 2
Here is a Python implementation of Merge Sort:
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
print(arr)
n = int(input())
arr = list(map(int, input().split()))
mergeSort(arr)
This script first checks if the array length is greater than 1. If it is, it divides the array into two halves and recursively sorts each half. Then, it merges the sorted halves back together, comparing elements from each half and adding the smaller one to the sorted array. After each merge operation, it prints the current state of the array.
Similar Questions
Given an array of size N having unique elements, implement Selection Sort.Note: Implement Selection Sort by selecting smallest element at every step.Input FormatThe first line of input contains an integer N - the size of an array. The second line contains the elements of the array.Output FormatFor each iteration of Selection Sort, print the array elements.Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput65 8 10 15 3 6Output3 8 10 15 5 63 5 10 15 8 63 5 6 15 8 103 5 6 8 15 10
Given an array of size N, implement Bubble Sort.Input FormatThe first line of input contains an integer N - the size of an array. The second line contains the elements of the array.Output FormatFor each iteration of Bubble Sort, print the array elements.Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput65 8 10 15 3 6Output5 8 10 3 6 155 8 3 6 10 155 3 6 8 10 153 5 6 8 10 153 5 6 8 10 15
Single File Programming QuestionProblem StatementGiven two arrays of size N, write a program to merge the arrays of integers into a single array by interleaving their elements. Input the size N and the elements of both arrays. Implement a solution that interleaves the elements alternately from both arrays and outputs the merged array.For Example, If the arrays are {12, 28, 54} and {48, 67, 35}, then the resultant array is {12, 48, 28, 67, 54, 35}.Note: This question helps in solving the technical coding tests in Infosys, Capgemini and TCS.Input format :The first line of input consists of an integer N, representing the size of the arrays.The second line consists of N space-separated elements of the first array.The third line consists of N space-separated elements of the second array.Output format :The output prints the resultant array.Code constraints :1 ≤ N ≤ 101 ≤ array elements ≤ 250Sample test cases :Input 1 :512 15 19 23 1834 31 78 59 65Output 1 :12 34 15 31 19 78 23 59 18 65 Input 2 :312 28 5448 67 35Output 2 :12 48 28 67 54 35
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.Merge nums1 and nums2 into a single array sorted in non-decreasing order.The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. Example 1:Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]Explanation: The arrays we are merging are [1,2,3] and [2,5,6].The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.Example 2:Input: nums1 = [1], m = 1, nums2 = [], n = 0Output: [1]Explanation: The arrays we are merging are [1] and [].The result of the merge is [1].Example 3:Input: nums1 = [0], m = 0, nums2 = [1], n = 1Output: [1]Explanation: The arrays we are merging are [] and [1].The result of the merge is [1].Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. Constraints:nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109 Follow up: Can you come up with an algorithm that runs in O(m + n) time?
What is the input for merging algorithm?a.Unsorted arrayb.Two arraysc. Integersd.Characters
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.