📄 merge sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://linux.wku.edu/~lamonml/algor/sort/merge.html -->
<HTML><HEAD><TITLE>Merge Sort</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META content="Michael Lamont" name=Author>
<META
content="Description, source code, algorithm analysis, and empirical results for merge sort."
name=Description>
<STYLE type=text/css>.BlueLink {
COLOR: #0000ff; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
A.BlueLink:hover {
COLOR: #0000ff; TEXT-DECORATION: underline
}
.TitleText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 24pt; TEXT-DECORATION: none
}
.HeadText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 18pt; TEXT-DECORATION: none
}
.BodyText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
.SectionText {
FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 14pt
}
.ComText {
FONT-FAMILY: courier,fixed; FONT-SIZE: 10pt
}
</STYLE>
<META content="MSHTML 5.00.3700.6699" name=GENERATOR></HEAD>
<BODY><A class=BlueLink href="http://linux.wku.edu/~lamonml/kb.html">Knowledge
Base</A> > <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/">Algorithms & Data Structures</A>
> <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/index.html">Sorting
Algorithms</A>
<P><B class=TitleText>Merge Sort</B>
<HR align=left noShade SIZE=1 width="40%">
<P></P>
<P class=BodyText><FONT class=SectionText><B>Algorithm Analysis</B></FONT><BR>
<P class=BodyText>The merge sort splits the list to be sorted into two equal
halves, and places them in separate arrays. Each array is recursively sorted,
and then merged back together to form the final sorted list. Like most recursive
sorts, the merge sort has an algorithmic complexity of <I>O</I>(<I>n</I> log
<I>n</I>).
<P class=BodyText>Elementary implementations of the merge sort make use of three
arrays - one for each half of the data set and one to store the sorted list in.
The below algorithm merges the arrays in-place, so only two arrays are required.
There are non-recursive versions of the merge sort, but they don't yield any
significant performance enhancement over the recursive algorithm on most
machines.
<P class=BodyText><B>Pros:</B> Marginally faster than the heap sort for larger
sets.<BR><B>Cons:</B> At least twice the memory requirements of the other sorts;
recursive.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Merge Sort Efficiency</I><BR><IMG
alt="Merge Sort Efficiency Graph" src="Merge Sort_files/merge.jpg"> </CENTER>
<P class=BodyText>The merge sort is slightly faster than the heap sort for
larger sets, but it requires twice the memory of the heap sort because of the
second array. This additional memory requirement makes it unattractive for most
purposes - the quick sort is a better choice most of the time and the heap sort
is a better choice for very large sets.
<P class=BodyText>Like the quick sort, the merge sort is recursive which can
make it a bad choice for applications that run on machines with limited memory.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic merge sort algorithm.
<P>
<CENTER>
<TABLE bgColor=#eeeeee border=0 cellSpacing=10 class=ComText width="90%">
<TBODY>
<TR>
<TD><FONT class=ComText><PRE><B>void</B> mergeSort(<B>int</B> numbers[], <B>int</B> temp[], <B>int</B> array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
<B>void</B> m_sort(<B>int</B> numbers[], <B>int</B> temp[], <B>int</B> left, <B>int</B> right)
{
<B>int</B> mid;
<B>if</B> (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
<B>void</B> merge(<B>int</B> numbers[], <B>int</B> temp[], <B>int</B> left, <B>int</B> mid, <B>int</B> right)
{
<B>int</B> i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
<B>while</B> ((left <= left_end) && (mid <= right))
{
<B>if</B> (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
<B>else</B>
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
<B>while</B> (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
<B>while</B> (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
<B>for</B> (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the merge sort
may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/merge.c">downloaded here</A>.
</P>
<HR align=center noShade SIZE=1 width="100%">
<A class=BlueLink href="http://linux.wku.edu/~lamonml/">Michael's
Homepage</A> <A class=BlueLink
href="http://linux.wku.edu/">WKU-Linux</A> </BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -