-
Notifications
You must be signed in to change notification settings - Fork 0
/
parallel-merge-sort.html
133 lines (119 loc) · 6.45 KB
/
parallel-merge-sort.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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=endge, chrome=IE8" />
<meta name="viewport" content="initial-scale=1.0, width=device-width, user-scalable=no" />
<title>Parallel Merge Sort — Titleless Sights</title>
<!--[if lte IE 8]><script type="text/javascript" src="http://james0zan.github.io/theme/js/html5shiv.js"></script><![endif]-->
<link rel="stylesheet" type="text/css" href="http://james0zan.github.io/theme/css/skeleton.css" />
<link rel="stylesheet" type="text/css" href="http://james0zan.github.io/theme/css/theme.css" />
<link rel="shortcut icon" type="image/png" href="http://james0zan.github.io/favicon.png" />
<!--[if lte IE 8]><link rel="shortcut icon" type="image/x-icon" href="http://james0zan.github.io/favicon.ico" /><![endif]-->
<link rel="alternate" type="application/atom+xml"
title="Titleless Sights — Flux Atom"
href="http://james0zan.github.io/feeds/atom.xml" />
<style>
li {
margin: 10px 0;
}
</style>
<meta name="author" content="Mingxing Zhang" />
<meta name="keywords" content="parallel, algorithm" />
<link rel="stylesheet" media="not print" type="text/css" href="http://james0zan.github.io/theme/css/pygments.css" />
</head>
<body>
<div id="page">
<header id="page-head">
<h1>
<a href="http://james0zan.github.io/index.html">Titleless Sights</a>
</h1>
</header>
<div id="page-body">
<article class="post" id="page-main" role="main">
<header class="post-header">
<h1>
<a rel="bookmark"
href="http://james0zan.github.io/parallel-merge-sort.html"
title="Lien permanent vers «Parallel Merge Sort»">
Parallel Merge Sort
</a>
</h1>
<div class="meta">
<!-- includes/article_meta.html -->
On <time datetime="2013-04-27T00:00:00">Sab 27 Aprile 2013</time>
in <em><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></em>
by <a href="http://james0zan.github.io/author/mingxing-zhang.html">Mingxing Zhang</a> <br />Tags: <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/parallel.html">parallel</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/algorithm.html">algorithm</a></span> </div>
</header>
<div class="post-content">
<p><em>URL:</em> <a class="reference external" href="http://coldattic.info/shvedsky/pro/blogs/a-foo-walks-into-a-bar/posts/49">http://coldattic.info/shvedsky/pro/blogs/a-foo-walks-into-a-bar/posts/49</a></p>
<p>I used to think that the "merge" step of merge sort cannot be efficiently parallelized, because the fact that an element belongs to the tail of one sorted array could not even guarrantee that it won't rank first in the other sorted arrary.</p>
<p>But this article illustrates that we can get across this obstacle by doing some binary search in advence.</p>
<p>And even better, this algorithm preserves merges sort's ability to be a external sort.</p>
</div>
<footer class="post-footer">
<div class="meta">
<!-- includes/article_meta.html -->
On <time datetime="2013-04-27T00:00:00">Sab 27 Aprile 2013</time>
in <em><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></em>
by <a href="http://james0zan.github.io/author/mingxing-zhang.html">Mingxing Zhang</a> <br />Tags: <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/parallel.html">parallel</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/algorithm.html">algorithm</a></span> </div>
</footer>
</article> <!-- /#page-main -->
<aside id="page-side">
<!-- begin includes/sidebar.html -->
<nav>
<h3>Pages</h3>
<ul>
<li><a href="http://james0zan.github.io/index.html">Home</a></li>
<li><a href="http://james0zan.github.io/category/blog.html">Blog</a></li>
<li><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></li>
</ul>
</nav>
<nav>
<h3>Projects</h3>
<ul>
<li><a href="http://james0zan.github.io/AI.html">AI</a></li>
</ul>
</nav>
<nav>
<h3>Meta</h3>
<ul>
<li><a href="http://james0zan.github.io/archives.html">Archives</a></li>
<li><a href="http://james0zan.github.io/tags.html">Tags</a></li>
</ul>
</nav>
<nav>
<h3>Contacts</h3>
<ul>
<li><a href="mailto:[email protected]">Gmail</a></li>
<li><a href="https://github.com/james0zan">Github</a></li>
<li><a href="http://www.linkedin.com/profile/view?id=80873276">Linkedin</a></li>
</ul>
<h3>Feeds</h3>
<ul>
<li><a href="http://james0zan.github.io/feeds/atom.xml">Atom</a></li>
<li><a href="http://james0zan.github.io/feeds/blog.atom.xml">Blog Feeds</a></li>
<li><a href="http://james0zan.github.io/feeds/bookmark.atom.xml">Bookmark Feeds</a></li>
</ul>
</nav>
<!-- end includes/sidebar.html --></aside> <!-- /#page-side -->
</div> <!-- /#page-body -->
<footer id="page-foot">
<p>
Powered by <a href="http://pelican.readthedocs.org">Pelican</a>; Theme from <a href="http://blog.1flow.net/">1flow team</a>.
</p>
<p><a id="github-link" href="https://github.com/james0zan/james0zan.github.io">Fork me on Github</a></p> </footer>
</div> <!-- /#page -->
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-40495434-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script');
ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</body>
</html>