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 map data structure?

652


What does simulation of queues mean?

767


What is the minimum number of queues needed when implementing a priority queue?

784


Which interfaces are implemented by concurrentskiplistset?

675


Can arraylist contain duplicates?

651


How many null values are allowed in a set?

668


What is non linear data structure with example?

682


How many types of priority queue are there?

705


How is a queue works?

741


Does hashmap preserve insertion order?

693


Can treemap have null values?

695


What is the best time complexity of bubble sort?

719


What are arrays give example?

710


What is the best data structure and algorithm to implement cache?

744


Why do we need arrays if all the operations that are performed on arrays can be performed on arraylist?

645