Difference between revisions of "Interview Preparation Merge Sort"
Proj user18 (talk | contribs) (Created page with "Algorithm for implementation of insertion sort is as follows a. Start from index 1. b. compare higher index element with all the elements at smaller index. c. If element at...") |
Proj user18 (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | Algorithm for implementation of | + | Algorithm for implementation of merge sort is as follows |
| − | a. | + | 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. | + | b. Starting from leaf node traverse the same route backward: |
| + | b.1. Compare the last two nodes. | ||
| + | b.2. 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 temporary buffer. | ||
| − | c. | + | c. Repeat step b until all the elements are copied to temporary buffer. |
| − | d. Store | + | d. Store all the elements in the temporary buffer back the main array. |
| − | |||
| − | |||
For an array with n number of elements, | For an array with n number of elements, | ||
| − | Best case complexity = O(n). | + | 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- | |
Revision as of 12:31, 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: b.1. Compare the last two nodes. b.2. 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 temporary buffer.
c. Repeat step b until all the elements are copied to 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-
