-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathmerge-sort.html
More file actions
354 lines (298 loc) · 73.9 KB
/
merge-sort.html
File metadata and controls
354 lines (298 loc) · 73.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Merge Sort</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Merge Sort Basics, Merge Sort Implementation in Go, Merge Sort Implementation in C & C#, Merge Sort Implementation in Java, Merge Sort Implementation in Python, Bottoms-up Java Implementation">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Merge Sort">
<meta property="og:description" content="Merge Sort Basics, Merge Sort Implementation in Go, Merge Sort Implementation in C & C#, Merge Sort Implementation in Java, Merge Sort Implementation in Python, Bottoms-up Java Implementation">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/merge-sort.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Merge Sort">
<meta name="twitter:description" content="Merge Sort Basics, Merge Sort Implementation in Go, Merge Sort Implementation in C & C#, Merge Sort Implementation in Java, Merge Sort Implementation in Python, Bottoms-up Java Implementation">
<meta name="twitter:url" content="/algorithm/merge-sort.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/56.9df27e42.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" aria-current="page" class="active sidebar-link">Merge Sort</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#merge-sort-basics" class="sidebar-link">Merge Sort Basics</a></li><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#merge-sort-implementation-in-go" class="sidebar-link">Merge Sort Implementation in Go</a></li><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#merge-sort-implementation-in-c-c" class="sidebar-link">Merge Sort Implementation in C & C#</a></li><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#merge-sort-implementation-in-java" class="sidebar-link">Merge Sort Implementation in Java</a></li><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#merge-sort-implementation-in-python" class="sidebar-link">Merge Sort Implementation in Python</a></li><li class="sidebar-sub-header"><a href="/algorithm/merge-sort.html#bottoms-up-java-implementation" class="sidebar-link">Bottoms-up Java Implementation</a></li></ul></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="merge-sort"><a href="#merge-sort" class="header-anchor">#</a> Merge Sort</h1> <h2 id="merge-sort-basics"><a href="#merge-sort-basics" class="header-anchor">#</a> Merge Sort Basics</h2> <p>Merge Sort is a divide-and-conquer algorithm. It divides the input list of length n in half successively until there are n lists of size 1. Then, pairs of lists are merged together with the smaller first element among the pair of lists being added in each step. Through successive merging and through comparison of first elements, the sorted list is built.</p> <p><strong>An example:</strong></p> <p><a href="http://i.stack.imgur.com/Bs29u.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/Bs29u.png" alt="Merge Sort example"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>Time Complexity</strong>: <code>T(n) = 2T(n/2) + Θ(n)</code></p> <p>The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is <code>Θ(nLogn)</code>.
Time complexity of <strong>Merge Sort</strong> is <code>Θ(nLogn)</code> in all 3 cases (<strong>worst, average and best</strong>) as merge sort always divides the array in two halves and take linear time to merge two halves.</p> <p><strong>Auxiliary Space</strong>: <code>O(n)</code></p> <p><strong>Algorithmic Paradigm</strong>: Divide and Conquer</p> <p><strong>Sorting In Place</strong>: Not in a typical implementation</p> <p><strong>Stable</strong>: Yes</p> <h2 id="merge-sort-implementation-in-go"><a href="#merge-sort-implementation-in-go" class="header-anchor">#</a> Merge Sort Implementation in Go</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>package main
<span class="token keyword">import</span> <span class="token module"><span class="token string">"fmt"</span></span>
func <span class="token function">mergeSort</span><span class="token punctuation">(</span>a <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span><span class="token punctuation">)</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token operator"><</span> <span class="token number">2</span> <span class="token punctuation">{</span>
<span class="token keyword">return</span> a
<span class="token punctuation">}</span>
m <span class="token operator">:</span><span class="token operator">=</span> <span class="token punctuation">(</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span>
f <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span><span class="token operator">:</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span>
s <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>m<span class="token operator">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token keyword">return</span> <span class="token function">merge</span><span class="token punctuation">(</span>f<span class="token punctuation">,</span> s<span class="token punctuation">)</span>
<span class="token punctuation">}</span>
func <span class="token function">merge</span><span class="token punctuation">(</span>f <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span><span class="token punctuation">,</span> s <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span><span class="token punctuation">)</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span> <span class="token punctuation">{</span>
var i<span class="token punctuation">,</span> j <span class="token keyword">int</span>
size <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>f<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
a <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span><span class="token punctuation">,</span> size<span class="token punctuation">,</span> size<span class="token punctuation">)</span>
<span class="token keyword">for</span> z <span class="token operator">:</span><span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> z <span class="token operator"><</span> size<span class="token punctuation">;</span> z<span class="token operator">++</span> <span class="token punctuation">{</span>
lenF <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>f<span class="token punctuation">)</span>
lenS <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
<span class="token keyword">if</span> i <span class="token operator">></span> lenF<span class="token operator">-</span><span class="token number">1</span> <span class="token operator">&&</span> j <span class="token operator"><=</span> lenS<span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
a<span class="token punctuation">[</span>z<span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
j<span class="token operator">++</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> j <span class="token operator">></span> lenS<span class="token operator">-</span><span class="token number">1</span> <span class="token operator">&&</span> i <span class="token operator"><=</span> lenF<span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
a<span class="token punctuation">[</span>z<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
i<span class="token operator">++</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"><</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span>
a<span class="token punctuation">[</span>z<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
i<span class="token operator">++</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
a<span class="token punctuation">[</span>z<span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
j<span class="token operator">++</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> a
<span class="token punctuation">}</span>
func <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
a <span class="token operator">:</span><span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token keyword">int</span><span class="token punctuation">{</span><span class="token number">75</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">34</span><span class="token punctuation">,</span> <span class="token number">45</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">123</span><span class="token punctuation">,</span> <span class="token number">32</span><span class="token punctuation">,</span> <span class="token number">56</span><span class="token punctuation">,</span> <span class="token number">32</span><span class="token punctuation">,</span> <span class="token number">99</span><span class="token punctuation">,</span> <span class="token number">123</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">86</span><span class="token punctuation">,</span> <span class="token number">33</span><span class="token punctuation">}</span>
fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span>
fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token function">mergeSort</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="merge-sort-implementation-in-c-c"><a href="#merge-sort-implementation-in-c-c" class="header-anchor">#</a> Merge Sort Implementation in C & C#</h2> <p><strong>C Merge Sort</strong></p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">merge</span><span class="token punctuation">(</span><span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> m<span class="token punctuation">,</span><span class="token keyword">int</span> h<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> arr1<span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">,</span>arr2<span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// Two temporary arrays to</span>
hold the two arrays to be merged
<span class="token keyword">int</span> n1<span class="token punctuation">,</span>n2<span class="token punctuation">,</span>i<span class="token punctuation">,</span>j<span class="token punctuation">,</span>k<span class="token punctuation">;</span>
n1<span class="token operator">=</span>m<span class="token operator">-</span>l<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
n2<span class="token operator">=</span>h<span class="token operator">-</span>m<span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><</span>n1<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
arr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>l<span class="token operator">+</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator"><</span>n2<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
arr2<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>m<span class="token operator">+</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
arr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">9999</span><span class="token punctuation">;</span> <span class="token comment">// To mark the end of each temporary array</span>
arr2<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">9999</span><span class="token punctuation">;</span>
i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>k<span class="token operator">=</span>l<span class="token punctuation">;</span> k<span class="token operator"><=</span>h<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//process of combining two sorted arrays</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>arr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator"><=</span>arr2<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>
arr<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span>arr1<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">else</span>
arr<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span>arr2<span class="token punctuation">[</span>j<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">merge_sort</span><span class="token punctuation">(</span><span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token keyword">int</span> low<span class="token punctuation">,</span><span class="token keyword">int</span> high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> mid<span class="token punctuation">;</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>low<span class="token operator"><</span>high<span class="token punctuation">)</span> <span class="token punctuation">{</span>
mid<span class="token operator">=</span><span class="token punctuation">(</span>low<span class="token operator">+</span>high<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
<span class="token comment">// Divide and Conquer</span>
<span class="token function">merge_sort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>low<span class="token punctuation">,</span>mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">merge_sort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>high<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// Combine</span>
<span class="token function">merge</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>low<span class="token punctuation">,</span>mid<span class="token punctuation">,</span>high<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>C# Merge Sort</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MergeSort</span>
<span class="token punctuation">{</span>
<span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">Merge</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i<span class="token punctuation">,</span> j<span class="token punctuation">;</span>
var n1 <span class="token operator">=</span> m <span class="token operator">-</span> l <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
var n2 <span class="token operator">=</span> r <span class="token operator">-</span> m<span class="token punctuation">;</span>
var left <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>n1<span class="token punctuation">]</span><span class="token punctuation">;</span>
var right <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>n2<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n1<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
left<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> input<span class="token punctuation">[</span>l <span class="token operator">+</span> i<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n2<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
right<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> input<span class="token punctuation">[</span>m <span class="token operator">+</span> j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
var k <span class="token operator">=</span> l<span class="token punctuation">;</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> n1 <span class="token operator">&&</span> j <span class="token operator"><</span> n2<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>left<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"><=</span> right<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
input<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> left<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
i<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
<span class="token punctuation">{</span>
input<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> right<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
j<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
k<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> n1<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
input<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> left<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
i<span class="token operator">++</span><span class="token punctuation">;</span>
k<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>j <span class="token operator"><</span> n2<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
input<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> right<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
j<span class="token operator">++</span><span class="token punctuation">;</span>
k<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">SortMerge</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator"><</span> r<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> m <span class="token operator">=</span> l <span class="token operator">+</span> <span class="token punctuation">(</span>r <span class="token operator">-</span> l<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>
<span class="token function">SortMerge</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">SortMerge</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">Merge</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token function">Main</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">SortMerge</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> input<span class="token punctuation">.</span>Length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> input<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="merge-sort-implementation-in-java"><a href="#merge-sort-implementation-in-java" class="header-anchor">#</a> Merge Sort Implementation in Java</h2> <p>Below there is the implementation in Java using a generics approach. It is the same algorithm, which is presented above.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">public</span> interface InPlaceSort<span class="token operator"><</span>T extends Comparable<span class="token operator"><</span>T<span class="token operator">>></span> <span class="token punctuation">{</span>
<span class="token keyword">void</span> <span class="token function">sort</span><span class="token punctuation">(</span><span class="token keyword">final</span> T<span class="token punctuation">[</span><span class="token punctuation">]</span> elements<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MergeSort</span> <span class="token operator"><</span> T extends Comparable <span class="token operator"><</span> T <span class="token operator">>></span> implements InPlaceSort <span class="token operator"><</span> T <span class="token operator">></span> <span class="token punctuation">{</span>
@Override
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">sort</span><span class="token punctuation">(</span>T<span class="token punctuation">[</span><span class="token punctuation">]</span> elements<span class="token punctuation">)</span> <span class="token punctuation">{</span>
T<span class="token punctuation">[</span><span class="token punctuation">]</span> arr <span class="token operator">=</span> <span class="token punctuation">(</span>T<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">new</span> Comparable<span class="token punctuation">[</span>elements<span class="token punctuation">.</span>length<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token function">sort</span><span class="token punctuation">(</span>elements<span class="token punctuation">,</span> arr<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> elements<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// We check both our sides and then merge them</span>
<span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">sort</span><span class="token punctuation">(</span>T<span class="token punctuation">[</span><span class="token punctuation">]</span> elements<span class="token punctuation">,</span> T<span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>low <span class="token operator">>=</span> high<span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> mid <span class="token operator">=</span> low <span class="token operator">+</span> <span class="token punctuation">(</span>high <span class="token operator">-</span> low<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>
<span class="token function">sort</span><span class="token punctuation">(</span>elements<span class="token punctuation">,</span> arr<span class="token punctuation">,</span> low<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">sort</span><span class="token punctuation">(</span>elements<span class="token punctuation">,</span> arr<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> high<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">merge</span><span class="token punctuation">(</span>elements<span class="token punctuation">,</span> arr<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">merge</span><span class="token punctuation">(</span>T<span class="token punctuation">[</span><span class="token punctuation">]</span> a<span class="token punctuation">,</span> T<span class="token punctuation">[</span><span class="token punctuation">]</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">int</span> i <span class="token operator">=</span> low<span class="token punctuation">;</span>
<span class="token keyword">int</span> j <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token comment">// We select the smallest element of the two. And then we put it into b</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> low<span class="token punctuation">;</span> k <span class="token operator"><=</span> high<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator"><=</span> mid <span class="token operator">&&</span> j <span class="token operator"><=</span> high<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">compareTo</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
b<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> a<span class="token punctuation">[</span>j<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
b<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> a<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">></span> high <span class="token operator">&&</span> i <span class="token operator"><=</span> mid<span class="token punctuation">)</span> <span class="token punctuation">{</span>
b<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> a<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">></span> mid <span class="token operator">&&</span> j <span class="token operator"><=</span> high<span class="token punctuation">)</span> <span class="token punctuation">{</span>
b<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> a<span class="token punctuation">[</span>j<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> n <span class="token operator">=</span> low<span class="token punctuation">;</span> n <span class="token operator"><=</span> high<span class="token punctuation">;</span> n<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
a<span class="token punctuation">[</span>n<span class="token punctuation">]</span> <span class="token operator">=</span> b<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">}</span><span class="token punctuation">}</span>
</code></pre></div><h2 id="merge-sort-implementation-in-python"><a href="#merge-sort-implementation-in-python" class="header-anchor">#</a> Merge Sort Implementation in Python</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>def <span class="token function">merge</span><span class="token punctuation">(</span>X<span class="token punctuation">,</span> Y<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token string">" merge two sorted lists "</span>
p1 <span class="token operator">=</span> p2 <span class="token operator">=</span> <span class="token number">0</span>
out <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
<span class="token keyword">while</span> p1 <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>X<span class="token punctuation">)</span> <span class="token operator">and</span> p2 <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>Y<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> X<span class="token punctuation">[</span>p1<span class="token punctuation">]</span> <span class="token operator"><</span> Y<span class="token punctuation">[</span>p2<span class="token punctuation">]</span><span class="token operator">:</span>
out<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>X<span class="token punctuation">[</span>p1<span class="token punctuation">]</span><span class="token punctuation">)</span>
p1 <span class="token operator">+=</span> <span class="token number">1</span>
<span class="token keyword">else</span><span class="token operator">:</span>
out<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>Y<span class="token punctuation">[</span>p2<span class="token punctuation">]</span><span class="token punctuation">)</span>
p2 <span class="token operator">+=</span> <span class="token number">1</span>
out <span class="token operator">+=</span> X<span class="token punctuation">[</span>p1<span class="token operator">:</span><span class="token punctuation">]</span> <span class="token operator">+</span> Y<span class="token punctuation">[</span>p2<span class="token operator">:</span><span class="token punctuation">]</span>
<span class="token keyword">return</span> out
def <span class="token function">mergeSort</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span> <span class="token operator"><=</span> <span class="token number">1</span><span class="token operator">:</span>
<span class="token keyword">return</span> A
<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">2</span><span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token function">sorted</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span>
mid <span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span>
<span class="token keyword">return</span> <span class="token function">merge</span><span class="token punctuation">(</span><span class="token function">mergeSort</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span><span class="token operator">:</span>mid<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>mid<span class="token operator">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token keyword">if</span> __name__ <span class="token operator">==</span> <span class="token string">"__main__"</span><span class="token operator">:</span>
<span class="token macro property"><span class="token directive-hash">#</span> <span class="token expression">Generate <span class="token number">20</span> random numbers <span class="token operator">and</span> sort them</span></span>
A <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token function">randint</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">100</span><span class="token punctuation">)</span> <span class="token keyword">for</span> i in <span class="token function">xrange</span><span class="token punctuation">(</span><span class="token number">20</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
print <span class="token function">mergeSort</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span>
</code></pre></div><h2 id="bottoms-up-java-implementation"><a href="#bottoms-up-java-implementation" class="header-anchor">#</a> Bottoms-up Java Implementation</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MergeSortBU</span> <span class="token punctuation">{</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> Integer<span class="token punctuation">[</span><span class="token punctuation">]</span> array <span class="token operator">=</span> <span class="token punctuation">{</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">,</span> <span class="token number">15</span><span class="token punctuation">,</span> <span class="token number">20</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">30</span><span class="token punctuation">,</span> <span class="token number">70</span><span class="token punctuation">,</span> <span class="token number">60</span><span class="token punctuation">,</span><span class="token number">80</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">67</span><span class="token punctuation">,</span><span class="token number">54</span><span class="token punctuation">,</span><span class="token number">51</span><span class="token punctuation">,</span><span class="token number">52</span><span class="token punctuation">,</span><span class="token number">24</span><span class="token punctuation">,</span><span class="token number">54</span><span class="token punctuation">,</span><span class="token number">7</span> <span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">public</span> <span class="token function">MergeSortBU</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token punctuation">}</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">merge</span><span class="token punctuation">(</span>Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> arrayToSort<span class="token punctuation">,</span> Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> aux<span class="token punctuation">,</span> <span class="token keyword">int</span> lo<span class="token punctuation">,</span><span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> hi<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> index <span class="token operator"><</span> arrayToSort<span class="token punctuation">.</span>length<span class="token punctuation">;</span> index<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
aux<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">=</span> arrayToSort<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> i <span class="token operator">=</span> lo<span class="token punctuation">;</span>
<span class="token keyword">int</span> j <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> lo<span class="token punctuation">;</span> k <span class="token operator"><=</span> hi<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">></span> mid<span class="token punctuation">)</span>
arrayToSort<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> aux<span class="token punctuation">[</span>j<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">></span> hi<span class="token punctuation">)</span>
arrayToSort<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> aux<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isLess</span><span class="token punctuation">(</span>aux<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> aux<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
arrayToSort<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> aux<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
arrayToSort<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> aux<span class="token punctuation">[</span>j<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">sort</span><span class="token punctuation">(</span>Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> arrayToSort<span class="token punctuation">,</span> Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> aux<span class="token punctuation">,</span> <span class="token keyword">int</span> lo<span class="token punctuation">,</span> <span class="token keyword">int</span> hi<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">int</span> N <span class="token operator">=</span> arrayToSort<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> sz <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> sz <span class="token operator"><</span> N<span class="token punctuation">;</span> sz <span class="token operator">=</span> sz <span class="token operator">+</span> sz<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> low <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> low <span class="token operator"><</span> N<span class="token punctuation">;</span> low <span class="token operator">=</span> low <span class="token operator">+</span> sz <span class="token operator">+</span> sz<span class="token punctuation">)</span> <span class="token punctuation">{</span>
System<span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"Size:"</span><span class="token operator">+</span> sz<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">merge</span><span class="token punctuation">(</span>arrayToSort<span class="token punctuation">,</span> aux<span class="token punctuation">,</span> low<span class="token punctuation">,</span> low <span class="token operator">+</span> sz <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">,</span>Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>low <span class="token operator">+</span> sz <span class="token operator">+</span> sz <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> N <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">print</span><span class="token punctuation">(</span>arrayToSort<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> boolean <span class="token function">isLess</span><span class="token punctuation">(</span>Comparable a<span class="token punctuation">,</span> Comparable b<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">return</span> a<span class="token punctuation">.</span><span class="token function">compareTo</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token operator"><=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">print</span><span class="token punctuation">(</span>Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> array<span class="token punctuation">)</span> <span class="token punctuation">{</span>http<span class="token operator">:</span><span class="token comment">//stackoverflow.com/documentation/algorithm/5732/merge-sort#</span>
StringBuffer buffer <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">StringBuffer</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>http<span class="token operator">:</span><span class="token comment">//stackoverflow.com/documentation/algorithm/5732/merge-sort#</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>Comparable value <span class="token operator">:</span> array<span class="token punctuation">)</span> <span class="token punctuation">{</span>
buffer<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>value<span class="token punctuation">)</span><span class="token punctuation">;</span>
buffer<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span><span class="token string">' '</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
System<span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>buffer<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span>String<span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>
Comparable<span class="token punctuation">[</span><span class="token punctuation">]</span> aux <span class="token operator">=</span> <span class="token keyword">new</span> Comparable<span class="token punctuation">[</span>array<span class="token punctuation">.</span>length<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token function">print</span><span class="token punctuation">(</span>array<span class="token punctuation">)</span><span class="token punctuation">;</span>
MergeSortBU<span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span>array<span class="token punctuation">,</span> aux<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> array<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/merge-sort.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/bubble-sort.html" class="prev">
Bubble Sort
</a></span> <span class="next"><a href="/algorithm/insertion-sort.html">
Insertion Sort
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/56.9df27e42.js" defer></script>
</body>
</html>