merge

Given two sorted arrays of size m and n respectively (m » n), how to merge them together? (Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) Solution Consider A[m+1] and B[n+1] and C[m+n] (m»n and indexing starts from 1) [Read More]

Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort. The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set. [Read More]

Here is the program in cpp: #include <iostream.h> #include <conio.h> using namespace std; const int MAX1 = 5 ; const int MAX2 = 7 ; class array { private : int \*arr ; int size ; public : void create ( int sz ) ; void sort( ) ; void display( ) ; void merge ( array &a , array &b ) ; } ; // creates array of given size sz, dynamically void array :: create ( int sz ) { size = sz ; arr = new int$size$ ; int n ; for ( int i = 0 ; i < size ; i++ ) { cout << "\\nEnter the element no. [Read More]