Two Way Merge Sort - Hackerrank Problem Solution

Two Way Merge Sort

Hackerrank Problem Solution

PROBLEM STATEMENT

Merge sort is a sorting technique based on divide and conquer technique. You are given an array of integers in any order. Sort the elements of given array in ascending order using merge sort.

Input Format

The first line contains an integer, n , the size of the array

The second line contains n space-separated integers a[i].

Constraints

2<=n<=600 1<=a[i]<=2*10^6

Output Format

First line prints the space separated initial array element Sorted Array in new line

Sample Input 0

5
1 2 3 4 5

Sample Output 0

1 2 3 4 5
1 2 3 4 5

---

SOLUTION

#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", A[i]); printf("\n"); } int main() { int i,n; int arr[100]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&arr[i]); printArray(arr, n); mergeSort(arr, 0, n - 1); printArray(arr, n); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.