-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathimpl-mergesort.html
168 lines (151 loc) · 11.6 KB
/
impl-mergesort.html
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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2022-W11-4 02:12 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Implementing Merge Sort</title>
<meta name="author" content="Inanna" />
<meta name="description" content="Implementing merge sort in clojure." />
<meta name="generator" content="Org Mode" />
<link href="/site.css" rel="stylesheet" type="text/css" /><link href="images/website-icon.png" rel="icon" />
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
displayAlign: "center",
displayIndent: "0em",
"HTML-CSS": { scale: 100,
linebreaks: { automatic: "false" },
webFont: "TeX"
},
SVG: {scale: 100,
linebreaks: { automatic: "false" },
font: "TeX"},
NativeMML: {scale: 100},
TeX: { equationNumbers: {autoNumber: "AMS"},
MultLineWidth: "85%",
TagSide: "right",
TagIndent: ".8em"
}
});
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML"></script>
</head>
<body>
<div id="preamble" class="status">
<div><a href="/index.html"><img alt="An abstract logo representing a series of three assembly line stamping machines with the words CONS, DEV, and embalzoned in white on each machine." id="site-logo" src="/images/website-logo.png" /></a></div>
</div>
<div id="content" class="content">
<h1 class="title">Implementing Merge Sort</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org6ab24e6">Introduction</a></li>
<li><a href="#org9b6fe81">Algorithm</a></li>
<li><a href="#org14432f7">Implementation</a>
<ul>
<li><a href="#org5e1344c">Merge Function</a></li>
<li><a href="#org889ce29">Sort function</a></li>
</ul>
</li>
<li><a href="#org8a732dd">Conclusion</a></li>
</ul>
</div>
</div>
<div id="outline-container-org6ab24e6" class="outline-2">
<h2 id="org6ab24e6">Introduction</h2>
<div class="outline-text-2" id="text-org6ab24e6">
<p>
Mergesort is, in my opinion, the most elegant sorting algorithm out there and an early prelude the commonly used <a href="other/pessimal-algorithms-and-simplexity-analysis.pdf">multiply and surrender paradigm</a> which is extremely good at explaining things like the search time for a pair of glasses.
</p>
</div>
</div>
<div id="outline-container-org9b6fe81" class="outline-2">
<h2 id="org9b6fe81">Algorithm</h2>
<div class="outline-text-2" id="text-org9b6fe81">
<p>
So first let's imagine the easiest sort that we could possibly do, something so trivial even a computer could do it. That would be the case where you have to sort a list of two items, where you just compare one of the items to the other and then swap them if they are not correctly ordered. Therefore, to ensure we can work with this trivial case we simply reduce the entire list into a series of binary lists.
</p>
<div id="org5f38fb4" class="figure">
<p><img src="./images/msort1_ebc14103-49df-4f80-9cd2-1c203f99932b.png" alt="An image of a list being split in half three times." />
</p>
</div>
<p>
From here it is also trivial to merge these lists while keeping them sorted! You basically have a function, <code>merge</code> that takes two lists, <code>a</code> and <code>b</code> and then compares the head of the two lists. If the head of <code>a</code> is greater than the head of <code>b</code> it adds <code>a</code> to the list and then merges the remaining lists.
</p>
<div id="org3880016" class="figure">
<p><img src="./images/msort2_ebc14103-49df-4f80-9cd2-1c203f99932b.png" alt="A list being merged with ordering preserved." />
</p>
</div>
<p>
As you may have noticed the tree produced by the execution is similar to a <a href="impl-bin-tree.html#ID-7944f7ee-c24c-4b0d-8a23-457368b762ab">binary tree</a> with the depth of one side of the tree being (of course) \(log_2(n)\), but of course traversal of the entire list occurs at each level, so the total execution of it will be \(O(n\ log(n))\), far faster than bubble sort or any other naive algorithm. Unfortunately it has a space complexity usually of \(O(n^2)\) as well.<label class="sidenote-number" for="1"><sup>1</sup></label><input checked="checked" id="1" style="display:none" type="checkbox" /><span class="sidenote"><span class="sidenote-number"> 1</span> This also <i>can</i> be implemented as an in-place sort, with \(O(n)\) complexity, but it only really works with linked lists in that case, which is why <a href="impl-quicksort.html#ID-4c210f5a-7ba8-4715-8770-c5217dc6084a">quicksort</a> is far more popular in the real world, even if it is less beautiful.</span>
</p>
</div>
</div>
<div id="outline-container-org14432f7" class="outline-2">
<h2 id="org14432f7">Implementation</h2>
<div class="outline-text-2" id="text-org14432f7">
<p>
Now to implement it in code, in this case in clojure.
</p>
</div>
<div id="outline-container-org5e1344c" class="outline-3">
<h3 id="org5e1344c">Merge Function</h3>
<div class="outline-text-3" id="text-org5e1344c">
<p>
Here we define a simple variadic function that either takes the left and right lists (both assumed to be sorted) or takes a predicate that returns true should the first argument be lesser than the second. As you can see list destructuring is used to bind the various portions of the list to variables that can then be used.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">merge</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>left right<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>merge < left right<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>comp <span style="color: #bbb;">[</span>left-head & left-rest <span style="color: #E53935;">:as</span> left<span style="color: #bbb;">]</span> <span style="color: #bbb;">[</span>right-head & right-rest <span style="color: #E53935;">:as</span> right<span style="color: #bbb;">]</span><span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">cond</span> <span style="color: #bbb;">(</span>nil? right-head<span style="color: #bbb;">)</span> left
<span style="color: #bbb;">(</span>nil? left-head<span style="color: #bbb;">)</span> right
<span style="color: #bbb;">(</span>comp left-head right-head<span style="color: #bbb;">)</span> <span style="color: #bbb;">(</span>cons left-head <span style="color: #494949;">(</span>merge left-rest right<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #E53935;">:else</span> <span style="color: #bbb;">(</span>cons right-head <span style="color: #494949;">(</span>merge left right-rest<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Because of how the merge function works, even if the arguments provided are a list of one item and <code>nil</code> it will return the original list. Likewise, two lists of one item each are correctly processed and sorted.
</p>
</div>
</div>
<div id="outline-container-org889ce29" class="outline-3">
<h3 id="org889ce29">Sort function</h3>
<div class="outline-text-3" id="text-org889ce29">
<p>
And now we come to the sorting function which, in essence, first recursively partitions the list into two groups until a state is reached in which the length of the list is one or zero, at which point it then returns the sorted list in that case and then merges the lists that it returns.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">mergesort</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>coll<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>mergesort < coll<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>comp coll<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #bbb;">[</span>left <span style="color: #494949;">(</span>take <span style="color: #bbb;">(</span>/ <span style="color: #494949;">(</span>count coll<span style="color: #494949;">)</span> 2<span style="color: #bbb;">)</span> coll<span style="color: #494949;">)</span>
right <span style="color: #494949;">(</span>drop <span style="color: #bbb;">(</span>count left<span style="color: #bbb;">)</span> coll<span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span>apply merge comp
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #bbb;">(</span>> <span style="color: #494949;">(</span>count coll<span style="color: #494949;">)</span> 2<span style="color: #bbb;">)</span>
<span style="color: #bbb;">[</span><span style="color: #494949;">(</span>mergesort left<span style="color: #494949;">)</span> <span style="color: #494949;">(</span>mergesort right<span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">[</span>left right<span style="color: #bbb;">]</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org8a732dd" class="outline-2">
<h2 id="org8a732dd">Conclusion</h2>
<div class="outline-text-2" id="text-org8a732dd">
<p>
As you can see, merge sort is a very elegant and simple function that allows you to quickly sort lists. However, unfortunately, due to it's space complexity and inability to effectively sort arrays in place it has been largely relegated to the dustbin of histroy.
</p>
</div>
</div>
<!-- Footnotes --><!--
<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1" role="doc-backlink">1</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">This also <i>can</i> be implemented as an in-place sort, with \(O(n)\) complexity, but it only really works with linked lists in that case, which is why <a href="impl-quicksort.html#ID-4c210f5a-7ba8-4715-8770-c5217dc6084a">quicksort</a> is far more popular in the real world, even if it is less beautiful.</p></div></div>
--></div>
<div id="postamble" class="status">
<p class="date">Last Modified: 2022-W11-4 01:39</p><p class="creator">Generated Using: <a href="https://www.gnu.org/software/emacs/">Emacs</a> 27.2 (<a href="https://orgmode.org">Org</a> mode 9.4.6)</p><p class="license">Except where otherwise noted content on <a href="https://cons.dev">cons.dev</a> is licensed under a <a href="https://creativecommons.org/licenses/by-sa/4.0/" rel="license">Creative Commons Attribution-ShareAlike 4.0 International License</a>.</p>
</div>
</body>
</html>