Merge-Sort

Dr. Hakim Mellah

Department of Computer Science & Software Engineering
Concordia University, Montreal, Canada

These slides has been extracted, modified and updated from original slides of :
• Data Structures and Algorithms in Java, 5th edition. John Wiley& Sons, 2010. ISBN 978-0-470-38326-1.
• Dr. Hanna’s slides ([Link]

Copyright © 2010 Michael T. Goodrich, Roberto Tamassia

All rights reserved
Coverage
❑ Merge-Sort

7 29 4 → 2 4 7 9

72 → 2 7 94 → 4 9

7→7 2→2 9→9 4→4

Merge Sort 2
Divide-and-Conquer
❑ Divide-and conquer is a general algorithmic design
paradigm:
◼ Divide: divide the input data S in two disjoint
subsets S1 and S2
◼ Recur: solve the subproblems associated with S1
and S2
◼ Conquer: combine the solutions for S1 and S2 into a
solution for S

❑ The base case for the recursion are subproblems of

size 0 or 1. In these cases the problem can be solved
directly.
Merge Sort 3
Merge-Sort
❑ Merge-sort uses divide- Algorithm mergeSort(S, C)
and-conquer to perform the Input sequence S with n
sorting operation. elements, comparator C
Output sequence S sorted
❑ Merge-sort on an input according to C
sequence S with n if [Link]() > 1
elements consists of three (S1, S2)  partition(S, n/2)
steps: mergeSort(S1, C)
◼ Divide: partition S into two mergeSort(S2, C)
sequences S1 and S2 of S  merge(S1, S2)
about n2 elements each
◼ Recur: recursively sort S1
and S2
◼ Conquer: merge S1 and S2
into a unique sorted
sequence Merge Sort 4
Merging Two Sorted Sequences
❑ The conquer step of Algorithm merge(A, B)
merge-sort consists Input sequences A and B with
of merging two n2 elements each
sorted sequences A Output sorted sequence of A  B
and B into a sorted
sequence S S  empty sequence
containing the union while [Link]()  [Link]()
of the elements of A if [Link]().element() < [Link]().element()
and B. [Link]([Link]([Link]()))
else
❑ Merging two sorted [Link]([Link]([Link]()))
sequences, each while [Link]()
with n2 elements [Link]([Link]([Link]()))
and implemented by while [Link]()
means of a doubly [Link]([Link]([Link]()))
linked list, takes return S
O(n) time.
Merge Sort 5
Merge-Sort Tree
❑ An execution of merge-sort is depicted by a binary tree
◼ each node represents a recursive call of merge-sort and stores
 unsorted sequence before the execution and its partition
 sorted sequence at the end of the execution
◼ the root is the initial call
◼ the leaves are calls on subsequences of size 0 or 1

7 2  9 4
Divide
7  2 9  4

7 2 9 4
Merge Sort 6
Merge-Sort Tree

Recur & 2 4 7 9
Conquer
2 7 4 9

7 2 9 4

Merge Sort 7
Merge-Sort Tree
Example*:

*Reference: [Link]

Merge Sort 8
Execution Example
❑ Partition
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6

7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 9
Execution Example (cont.)
❑ Recursive call, partition
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 10
Execution Example (cont.)
❑ Recursive call, partition
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 11
Execution Example (cont.)
❑ Recursive call, base case
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 12
Execution Example (cont.)
❑ Recursive call, base case
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 13
Execution Example (cont.)
❑ Merge
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 14
Execution Example (cont.)
❑ Recursive call, …, base case, merge
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 15
Execution Example (cont.)
❑ Merge
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 8 6

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 16
Execution Example (cont.)
❑ Recursive call, …, merge, merge
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 6 8

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 17
Execution Example (cont.)
❑ Merge
7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9 3 8 6 1 → 1 3 6 8

72→2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6

7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1

Merge Sort 18
The Cost of Sorting Two Sorted Arrays
Algorithm merge(A1, A2, A)
Input sorted sequences A 1 and A2 and empty
❑ The algorithm to sequence A with sufficient size; all are
merge 2 sorted implemented as arrays
arrays (possibly of Output sorted sequence A containing A1  A2
different sizes) can ij0
be as follows:
while i < [Link]()  j < [Link]() do
if [Link](i) <= [Link](j) then
[Link]([Link](i))
ii+1
else
[Link]([Link](j))
jj+1
while i < [Link]() do
[Link]([Link](i))
ii+1
while j < [Link]() do
[Link]([Link](j))
Merge Sort jj+1 19
 The Cost of Sorting Two Sorted Arrays
❑ Example
0 1 2 3 4 5 6
A1 2 5 8 11 12 14 15
i
0 1 2 3 4 5 6
A2 3 9 10 18 19 22 25
j

0 1 2 3 4 5 6 0 7 8 9 10 11 12
A 2 3 5 8 9

❑ We compare the two current elements at the head of the two arrays (which are
pointed by i & j) then insert the smaller one in the final array.
❑ Hence, actual cost is O(n1) + O(n2) , where A1 has n1 elements and A2 has n2
elements ➔ total cost is hence O(n). Merge Sort 20
The Cost of Sorting Two Sorted Lists
❑ The algorithm is quite similar to the one for arrays (see Page
5 of these slides).

❑ Simply:
◼ As long as the two lists are not empty, compare the two entries pointed
by the head of the lists,
◼ Pickup the smaller one and insert it at the tail/end of the new list;
remove this item afterwards
◼ If any of the two lists is still not empty, iterate on it and insert its
remaining items at the tail of the

❑ Again, the actual cost is O(n1) + O(n2) , where n1 and n2 are the number
of elements in the two lists.

❑ Consequently, total cost to sort the two sorted lists is O(n).

Merge Sort 21
Analysis of Merge-Sort
❑ The height h of the merge-sort tree is O(log n)
◼ at each recursive call we divide in half the sequence,
❑ The overall amount or work done at the nodes of depth i is O(n)
◼ we partition and merge 2i sequences of size n2i
◼ we make 2i+1 recursive calls
❑ Thus, the total running time of merge-sort is O(n log n)

depth # of size
sequences
0 1 n

1 2 n2
i 2i n2i
… … …
Merge Sort 22
Merge-Sort vs. Heap-Sort
❑ Like heap-sort
◼ It uses a comparator

◼ It has O(n log n) running time.

 The cost to sort the elements at each level is O(n) and we

do that log n times.

❑ Unlike heap-sort
◼ It does not use an auxiliary priority queue

◼ It accesses data in a sequential manner (suitable to sort data

on a disk)

Merge Sort 23
Summary of Sorting Algorithms
Algorithm Time Notes
▪ slow
selection-sort O(n2) ▪ in-place
▪ for small data sets (< 1K)
▪ slow
insertion-sort O(n2) ▪ in-place
▪ for small data sets (< 1K)
▪ fast
heap-sort O(n log n) ▪ in-place
▪ for large data sets (1K — 1M)
▪ fast
merge-sort O(n log n) ▪ sequential data access
▪ for huge data sets (> 1M)
Merge Sort 24