Difference between revisions of "Interview Preparation Merge Sort"
Proj user18 (talk | contribs) |
Proj user18 (talk | contribs) |
||
| Line 5: | Line 5: | ||
b. Starting from leaf node traverse the same route backward: | b. Starting from leaf node traverse the same route backward: | ||
| − | + | * Compare the last two nodes. | |
| − | + | * Traverse each node whichever element in the node is smaller save the element in the temporary buffer first then save the element of the other node at incremented index in the temporary buffer. | |
| − | c. Repeat step b until all the elements are copied to temporary buffer. | + | c. Repeat step b until all the elements are copied to the temporary buffer. |
d. Store all the elements in the temporary buffer back the main array. | d. Store all the elements in the temporary buffer back the main array. | ||
Revision as of 12:34, 25 November 2016
Algorithm for implementation of merge sort is as follows
a. Divide the string into two half using formula (start index + end index)/2, where each half have a new start and end index till one element is left in the leaf node.
b. Starting from leaf node traverse the same route backward:
* Compare the last two nodes.
* Traverse each node whichever element in the node is smaller save the element in the temporary buffer first then save the element of the other node at incremented index in the temporary buffer.
c. Repeat step b until all the elements are copied to the temporary buffer.
d. Store all the elements in the temporary buffer back the main array.
For an array with n number of elements,
Best case complexity = Average case complexity = Worst case complexity = O(n log n).
For an animated model refer to following URL http://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-
