Mergesort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/merge-sort-1944 Openlearnware]</div> | <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/merge-sort-1944 Openlearnware]</div> | ||
</div> | </div> | ||
== General Information == | |||
'''Algorithmic problem:''' Sorting based on pairwise comparison | |||
'''Type of algorithm:''' recursion | |||
== Abstract View == | |||
'''Invariant:''' After a recursive call, the input sequence of this recursive call is sorted. | |||
'''Variant:''' For a recursive call on a subsequence <math>S'</math> of <math>S</math>, let <math>S_1'</math> and <math>S_2'</math> denote the subsequences of <math>S'</math> with which Mergesort is called recursively from that call. Then it is <math>|S_1'| \leq \lceil|S'| /2\rceil</math> and <math>|S_2'| \leq \lceil|S'| /2\rceil</math>. | |||
'''Break condition:''' The current subsequence of the recursive call is empty or a singleton. | |||
== Induction Basis == | |||
== Induction Step == | |||
== Complexity == | |||
Revision as of 20:59, 23 September 2014
General Information
Algorithmic problem: Sorting based on pairwise comparison
Type of algorithm: recursion
Abstract View
Invariant: After a recursive call, the input sequence of this recursive call is sorted.
Variant: For a recursive call on a subsequence [math]\displaystyle{ S' }[/math] of [math]\displaystyle{ S }[/math], let [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math] denote the subsequences of [math]\displaystyle{ S' }[/math] with which Mergesort is called recursively from that call. Then it is [math]\displaystyle{ |S_1'| \leq \lceil|S'| /2\rceil }[/math] and [math]\displaystyle{ |S_2'| \leq \lceil|S'| /2\rceil }[/math].
Break condition: The current subsequence of the recursive call is empty or a singleton.