Scribd
Upload
2 views3 pages

Merge Sort

The two-way merge technique combines two sorted arrays into a larger sorted array and is essential to the Merge Sort algorithm. It involves initializing pointers, comparing elements, and handling remaining elements after one array is exhausted. Use cases include Merge Sort, external sorting for large data, and efficient database join operations.

Uploaded by

S JAGADEESH BABU
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Merge Sort

The two-way merge technique combines two sorted arrays into a larger sorted array and is essential to the Merge Sort algorithm. It involves initializing pointers, comparing elements, and handling remaining elements after one array is exhausted. Use cases include Merge Sort, external sorting for large data, and efficient database join operations.

Uploaded by

S JAGADEESH BABU
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

The two-way merge is a technique for combining two sorted arrays into

a single, larger sorted array. It is the fundamental building block of


the Merge Sort algorithm, which recursively divides an unsorted list into
smaller sub-lists until they are trivially sorted (size 1) and then merges
them back together.

Core Logic of Two-Way Merging

1. Initialize Pointers: Use two pointers (indices) to track the current


element in each input array.

2. Compare and Select: Compare the elements at these pointers.


Copy the smaller value into the result array and move its respective
pointer forward.

3. Handle Remaining Elements: Once one array is exhausted, copy


all remaining elements from the other array directly into the result.

Example C Program

This program uses a merge function to combine two sorted arrays into a
third array.

#include <stdio.h>

// Function to perform two-way merging

void merge(int arr1[], int n1, int arr2[], int n2, int res[]) {

int i = 0, j = 0, k = 0;

// Compare elements from both arrays and insert the smaller one into
res[]

while (i < n1 && j < n2) {

if (arr1[i] <= arr2[j]) {

res[k++] = arr1[i++];

} else {

res[k++] = arr2[j++];

}
// Copy any remaining elements of arr1[]

while (i < n1) {

res[k++] = arr1[i++];

// Copy any remaining elements of arr2[]

while (j < n2) {

res[k++] = arr2[j++];

int main() {

int arr1[] = {1, 3, 5, 7};

int arr2[] = {2, 4, 6, 8, 10};

int n1 = sizeof(arr1) / sizeof(arr1[0]);

int n2 = sizeof(arr2) / sizeof(arr2[0]);

int res[n1 + n2];

merge(arr1, n1, arr2, n2, res);

printf("Merged Array: ");

for (int i = 0; i < n1 + n2; i++) {

printf("%d ", res[i]);

return 0;

}
Use Cases

 Merge Sort Algorithm: The "Divide and Conquer" sorting strategy


uses this to combine sorted sub-arrays.

 External Sorting: Used when data is too large to fit in memory and
must be merged from different disk files.

 Database Join Operations: Efficiently joining two pre-sorted


database tables.

You might also like