merge-sort.md (2592B)
1 +++ 2 title = "Merge sort" 3 template = "page-math.html" 4 +++ 5 6 # Merge sort 7 8 divide and conquer 9 10 algorithm 11 12 - sort() 13 - stop if sequence contains less than 1 element 14 - split sequence into two almost equal length parts 15 - sort(subsequences) 16 - merge(two sorted sublists) 17 - merging: 18 - loop while both sequences are nonempty 19 - compare first elements of both sequences 20 - remove smallest, move it to end of output sequence 21 - last: if one of sequences is empty, add other to tail of output sequence 22 23 <table> 24 <tbody align="center"> 25 <tr><td colspan="8">1,3,2,5,6,4,8,6</td></tr> 26 <tr><td colspan="4">1,3,2,5</td><td colspan="4">6,4,8,6</td></tr> 27 <tr><td colspan="2">1,3</td><td colspan="2">2,5</td><td colspan="2">6,4</td><td colspan="2">8,6</td></tr> 28 <tr><td>1</td><td>3</td><td>2</td><td>5</td><td>6</td><td>4</td><td>8</td><td>6</td></tr> 29 <tr><td colspan="2">1,3</td><td colspan="2">2,5</td><td colspan="2">4,6</td><td colspan="2">6,8</td></tr> 30 <tr><td colspan="4">1,2,3,5</td><td colspan="4">4,6,6,8</td></tr> 31 <tr><td colspan="8">1,2,3,4,5,6,6,8</td></tr> 32 </tbody> 33 </table> 34 35 *analysis* 36 merge tree for list with n elements: 37 38 - leaves: n 39 - levels: logn+1 40 - height: logn 41 - T(n) = cmerge ⋅ n 42 - merge is in ϴ(n), work per level is in ϴ(n) 43 - work total ≈ ϴ(n)(logn+1), because logn+1 layers 44 - T(n) = nlogn+n 45 46 shape of input is unimportant, as best case = worst case 47 time complexity in recurrence equations: 48 49 - divide is ϴ(1) 50 - conquer is recursive 51 - combine is ϴ(n) 52 - so: 53 54 $T(n)=\begin{cases} 55 c, & \text{if $n=1$}\\\\ 56 2T(\frac{n}{2})+cn, & \text{if $n > 1$} 57 \end{cases}$ 58 59 - solving the equation to find time complexity: 60 61 $\begin{aligned} 62 T(n) &= 2T(\frac{n}{2})+cn\\\\ 63 &= 2(2T(\frac{n}{4})+\frac{cn}{2})+cn&&[i=1]\\\\ 64 &= 4T(\frac{n}{4})+2cn&&[i=2]\\\\ 65 &= 4(2T(\frac{n}{8})+\frac{cn}{4})+2cn&&[i=3]\\\\ 66 &= 8T(\frac{n}{8})+3cn&&[i=4]\\\\ 67 &= \text{etc.}\\\\ 68 &= 2^iT(\frac{n}{2^i})+cni&&[i=n] 69 \end{aligned}$ 70 71 $\begin{aligned} 72 \text{base } &T(1) = 1\\\\ 73 \text{so } &\frac{n}{2^i}=1\\\\ 74 \text{when } &n=2^i &&(\frac{n}{n}=1)\\\\ 75 \text{hence } &i=\log{n} &&(i\text{ being the depth of the tree}) 76 \end{aligned}$ 77 78 - substituting: 79 80 $\begin{aligned} 81 2^i\\;T(\frac{n}{2^i})+cni &= 2^{\log{n}}\times T(\frac{n}{2^{\log{n}}})+cn\log{n}\\\\ 82 &= n\times c+cn\log{n} 83 \end{aligned}$ 84 85 so T(n) is of shape nlogn. Therefore T(n) is in ϴ(nlogn).