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
|
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1.5cm, top=2cm, bottom=2cm]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{setspace}
\setstretch{0.9}
\title{CS161 Notes - Merge Sort}
\author{Yuren Hao}
\date{\today}
\begin{document}
\maketitle
\section{Merge Sort}
Divide-and-conquer sorting algorithm: recursively divide array into halves, sort each half, then merge.
\textbf{Algorithm:}
\begin{enumerate}
\item \textbf{Divide:} Split $A[1..n]$ at midpoint $\lfloor n/2 \rfloor$
\item \textbf{Conquer:} Recursively sort both halves
\item \textbf{Combine:} Merge sorted halves
\end{enumerate}
\section{Pseudocode}
\textbf{MERGE-SORT}$(A, p, r)$:
\begin{enumerate}
\item \textbf{if} $p < r$:
\begin{itemize}
\item $q = \lfloor (p + r) / 2 \rfloor$
\item \textbf{MERGE-SORT}$(A, p, q)$
\item \textbf{MERGE-SORT}$(A, q + 1, r)$
\item \textbf{MERGE}$(A, p, q, r)$
\end{itemize}
\end{enumerate}
\textbf{MERGE}$(A, p, q, r)$:
\begin{enumerate}
\item $n_1 = q - p + 1$, $n_2 = r - q$
\item Create arrays $L[1..n_1 + 1]$, $R[1..n_2 + 1]$
\item Copy $A[p..q] \to L[1..n_1]$, $A[q+1..r] \to R[1..n_2]$
\item $L[n_1 + 1] = R[n_2 + 1] = \infty$
\item $i = j = 1$
\item \textbf{for} $k = p$ \textbf{to} $r$:
\begin{itemize}
\item \textbf{if} $L[i] \leq R[j]$: $A[k] = L[i++]$
\item \textbf{else}: $A[k] = R[j++]$
\end{itemize}
\end{enumerate}
\section{Complexity Analysis}
\textbf{Time:} $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$ (Master Theorem)
\textbf{Space:} $\Theta(n)$ auxiliary arrays + $\Theta(\log n)$ recursion stack = $\Theta(n)$
\section{Properties}
\textbf{Advantages:} Stable, predictable $O(n \log n)$, parallelizable
\textbf{Disadvantages:} $O(n)$ extra space, not in-place
\end{document}
|
