Explain about Merge Sort?

Answer Posted / rohit sah

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:
1. Divide Step
If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A1 and A2, each containing about half of the elements of A.
2. Recursion Step
Recursively sort array A1 and A2.
3. Conquer Step
Combine the elements back in A by merging the sorted arrays A1 and A2 into a sorted sequence.
We can visualize Merge-sort by means of binary tree where each node of the tree represents a recursive call and each external nodes represent individual elements of given array A. Such a tree is called Merge-sort tree. The heart of the Merge-sort algorithm is conquer step, which merge two sorted sequences into a single sorted sequence.

Is This Answer Correct ?    0 Yes 0 No



Post New Answer       View All Answers


Please Help Members By Posting Answers For Below Questions

What is concept of data structure?

638


State the difference between arrays and linked lists?

723


Write the stack overflow condition.

814


What is a pass in bubble sort?

686


Which one is the simplest sorting in data structure?

796


What are three common types of traversals?

642


What is lifo?

885


What is difference between arraylist and list?

657


What is data and data structure?

703


What is bubble sort algorithm?

763


What is hashing technique?

708


Data structure used to implement a menu

840


What is the difference between ienumerable and list?

638


What are different types of sorting techniques?

678


Which is faster hashmap or linkedhashmap?

696