Scribd
Upload
11 views82 pages

Merge and Quick Sort Algorithms Explained

The document describes sorting algorithms, specifically merge sort and quick sort. It provides an overview of the divide and conquer approach and explains how merge sort works by dividing the array into halves, recursively sorting each half, and then merging the sorted halves back together. The key steps of merge sort, including the merge process, are outlined in detail with an example.

Uploaded by

sankar_mca227390
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
11 views82 pages

Merge and Quick Sort Algorithms Explained

The document describes sorting algorithms, specifically merge sort and quick sort. It provides an overview of the divide and conquer approach and explains how merge sort works by dividing the array into halves, recursively sorting each half, and then merging the sorted halves back together. The key steps of merge sort, including the merge process, are outlined in detail with an example.

Uploaded by

sankar_mca227390
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Sorting Algorithms

Merge Sort
Quick Sort

Hairong Zhao
[Link]
New Jersey Institute of Technology
Overview
 Divide and Conquer

 Merge Sort

 Quick Sort

2
Divide and Conquer
1. Base Case, solve the problem directly
if it is small enough

2. Divide the problem into two or more


similar and smaller subproblems

3. Recursively solve the subproblems

4. Combine solutions to the subproblems


3
Divide and Conquer - Sort
Problem:
 Input: A[left..right] – unsorted array of integers

 Output: A[left..right] – sorted in non-decreasing


order

4
Divide and Conquer - Sort
1. Base case
at most one element (left ≥ right), return
2. Divide A into two subarrays: FirstPart, SecondPart
Two Subproblems:
sort the FirstPart
sort the SecondPart

3. Recursively
sort FirstPart
sort SecondPart

4. Combine sorted FirstPart and sorted SecondPart

5
Overview
 Divide and Conquer

 Merge Sort

 Quick Sort

6
Merge Sort: Idea

Divide into
A FirstPart SecondPart
two halves
Recursively
sort
FirstPart SecondPart

Merge

A is sorted!

7
Merge Sort: Algorithm
Merge-Sort (A, left, right)
if left ≥ right return
else
middle ← b(left+right)/2
Recursive Call
Merge-Sort(A, left, middle)
Merge-Sort(A, middle+1, right)
Merge(A, left, middle, right)

8
Merge-Sort: Merge
Sorted

A:

merge
Sorted Sorted
FirstPart SecondPart

A:

A[left] A[middle] A[right] 9


Merge-Sort: Merge Example

A: 2
5 3
5 7 28
15 8 30
1 4
6 5 14
10 6

L: R:
3 5 15 28 6 10 14 22

Temporary Arrays
10
Merge-Sort: Merge Example

A:
3
1 5 15 28 30 6 10 14

k=0

L: R:
3
2 15
3 28
7 30
8 6
1 10
4 14
5 22
6

i=0 j=0
11
Merge-Sort: Merge Example

A:
1 2
5 15 28 30 6 10 14

k=1

L: R:
3
2 5
3 15
7 28
8 6
1 10
4 14
5 22
6

i=0 j=1
12
Merge-Sort: Merge Example

A:
1 2 3 28 30
15 6 10 14

k=2

L: R:
2 3 7 8 6
1 10
4 14
5 22
6

i=1 j=1
13
Merge-Sort: Merge Example

A:
1 2 3 4 6 10 14

k=3

L: R:
2 3 7 8 6
1 10
4 14
5 22
6

i=2 j=1
14
Merge-Sort: Merge Example

A:
1 2 3 4 5 6 10 14

k=4

L: R:
2 3 7 8 6
1 10
4 14
5 22
6

i=2 j=2
15
Merge-Sort: Merge Example

A:
1 2 3 4 5 6 10 14

k=5

L: R:
2 3 7 8 6
1 10
4 14
5 22
6

i=2 j=3
16
Merge-Sort: Merge Example

A:
1 2 3 4 5 6 7 14

k=6

L: R:
2 3 7 8 6
1 10
4 14
5 22
6

i=2 j=4
17
Merge-Sort: Merge Example

A:
1 2 3 4 5 6 7 8
14

k=7

L: R:
3
2 5
3 15
7 28
8 6
1 10
4 14
5 22
6

i=3 j=4
18
Merge-Sort: Merge Example

A:
1 2 3 4 5 6 7 8

k=8

L: R:
3
2 5
3 15
7 28
8 6
1 10
4 14
5 22
6

i=4 j=4
19
Merge(A, left, middle, right)
1. n1 ← middle – left + 1
2. n2 ← right – middle
3. create array L[n1], R[n2]
4. for i ← 0 to n1-1 do L[i] ← A[left +i]
5. for j ← 0 to n2-1 do R[j] ← A[middle+j]
6. k ← i ← j ← 0
7. while i < n1 & j < n2
8. if L[i] < R[j]
9. A[k++] ← L[i++]
10. else
11. A[k++] ← R[j++]
12. while i < n1
13. A[k++] ← L[i++]
14. while j < n2
15. A[k++] ← R[j++] n = n1+n2
Space: n
20
Time : cn for some constant c
Merge-Sort(A, 0, 7)
Divide
A: 6 2 8 4 3 3 7 7 5 5 11

21
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 3) , divide
A: 3 7 5 1

6 2 88 44

22
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 1) , divide
A: 3 7 5 1

8 4

6 2
2

23
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 0) , base case
A: 3 7 5 1

8 4

24
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 0), return
A: 3 7 5 1

8 4

6 2

25
Merge-Sort(A, 0, 7)
Merge-Sort(A, 1, 1) , base case
A: 3 7 5 1

8 4

26
Merge-Sort(A, 0, 7)
Merge-Sort(A, 1, 1), return
A: 3 7 5 1

8 4

6 2

27
Merge-Sort(A, 0, 7)
Merge(A, 0, 0, 1)
A: 3 7 5 1

8 4

2 6

28
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 1), return
A: 3 7 5 1

2 6 8 4

29
Merge-Sort(A, 0, 7)
Merge-Sort(A, 2, 3) , divide
A: 3 7 5 1

2 6

8 4

30
Merge-Sort(A, 0, 7)
Merge-Sort(A, 2, 2), base case
A: 3 7 5 1

2 6

31
Merge-Sort(A, 0, 7)
Merge-Sort(A, 2, 2), return
A: 3 7 5 1

2 6

8 4

32
Merge-Sort(A, 0, 7)
Merge-Sort(A, 3, 3), base case
A:

2 6

33
Merge-Sort(A, 0, 7)
Merge-Sort(A, 3, 3), return
A: 3 7 5 1

2 6

8 4

34
Merge-Sort(A, 0, 7)
Merge(A, 2, 2, 3)
A: 3 7 5 1

2 6

4 8

35
Merge-Sort(A, 0, 7)
Merge-Sort(A, 2, 3), return
A: 3 7 5 1

2 6 4 8

36
Merge-Sort(A, 0, 7)
Merge(A, 0, 1, 3)
A: 3 7 5 1

2 4 6 8

37
Merge-Sort(A, 0, 7)
Merge-Sort(A, 0, 3), return
A: 2 4 6 8 3 7 5 1

38
Merge-Sort(A, 0, 7)
Merge-Sort(A, 4, 7)
A: 2 4 6 8

3 7 5 1

39
Merge-Sort(A, 0, 7)
Merge (A, 4, 5, 7)
A: 2 4 6 8

1 3 5 7

40
Merge-Sort(A, 0, 7)
Merge-Sort(A, 4, 7), return
A: 2 4 6 8 1 3 5 7

41
Merge-Sort(A, 0, 7)
Merge-Sort(A,
Merge(A, 0, 3, 0,
7)7), done!
A: 1 2 3 4 5 6 7 8

42
Merge-Sort Analysis
n cn

n/2 n/2 2 × cn/2 = cn

log n levels
n/4 n/4 n/4 n/4 4 × cn/4 = cn

n/2 × 2c = cn
2 2 2

Total: cn log n

• Total running time: (nlogn)


• Total Space:  (n)
43
Merge-Sort Summary
Approach: divide and conquer
Time
 Most of the work is in the merging
 Total time: (n log n)
Space:
 (n), more space than other sorts.

44
Overview
 Divide and Conquer

 Merge Sort

 Quick Sort

45
Quick Sort
 Divide:
 Pick any element p as the pivot, e.g, the first
element
 Partition the remaining elements into
FirstPart, which contains all elements < p
SecondPart, which contains all elements ≥ p

 Recursively sort the FirstPart and SecondPart

 Combine: no work is necessary since sorting


is done in place
46
Quick Sort
A: p
pivot Partition
FirstPart SecondPart

x<p p p≤x
Recursive call
Sorted Sorted
FirstPart SecondPart

x<p p p≤x

Sorted 47
Quick Sort
Quick-Sort(A, left, right)
if left ≥ right return
else
middle ← Partition(A, left, right)
Quick-Sort(A, left, middle–1 )
Quick-Sort(A, middle+1, right)
end if

48
Partition
A: p

A: p x<p p≤x

A:
p x<p p p≤x

49
Partition Example

A: 4 8 6 3 5 1 7 2

50
Partition Example

i=0

A: 4 8 6 3 5 1 7 2

j=1

51
Partition Example

i=0

A: 4 8 6 3 5 1 7 2

j=1

52
Partition Example

i=0

A: 4 8 6 3 5 1 7 2

j=2

53
Partition Example

i=0i=1

A: 4 8
3 6 3
8 5 1 7 2

j=3

54
Partition Example

i=1

A: 4 3 6 8 5 1 7 2

j=4

55
Partition Example

i=1

A: 4 3 6 8 5 1 7 2

j=5

56
Partition Example

i=2

A: 4 3 1
6 8 5 6
1 7 2

j=5

57
Partition Example

i=2

A: 4 3 1 8 5 6 7 2

j=6

58
Partition Example

i=2i=3

A: 4 3 1 2
8 5 6 7 8
2

j=7

59
Partition Example

i=3

A: 4 3 1 2 5 6 7 8

j=8

60
Partition Example

i=3

A: 24 3 1 4
2 5 6 7 8

61
Partition Example

pivot in
correct position

A: 2 3 1 4 5 6 7 8

x<4 4≤x

62
Partition(A, left, right)
1. x ← A[left]
2. i ← left
3. for j ← left+1 to right
4. if A[j] < x then
5. i ← i + 1
6. swap(A[i], A[j])
7. end if
8. end for j
9. swap(A[i], A[left])
10. return i
n = right – left +1
Time: cn for some constant c
63
Space: constant
Quick-Sort(A, 0, 7)
Partition
A: 2
4 3
8 1
6 34 55 16 77 28

64
Quick-Sort(A, 0, 7)
Quick-Sort(A, 0, 2) , partition
A: 4 5 6 7 8

21 2
3 31

65
Quick-Sort(A, 0, 7)
Quick-Sort(A, 0, 0) , base
returncase
4 5 6 7 8

1 2 3

66
Quick-Sort(A, 0, 7)
Quick-Sort(A, 1, 1) , base case
4 5 6 7 8

1 2

67
Quick-Sort(A, 0, 7)
Quick-Sort(A,2,
Quick-Sort(A, 0,2),
2),return
return
1 2 3 4 5 6 7 8

1 2 3

68
Quick-Sort(A, 0, 7)
Quick-Sort(A,2,
Quick-Sort(A, 4,2),
7) ,return
partition
1 2 3 4

55 6 7 8

69
Quick-Sort(A, 0, 7)
Quick-Sort(A, 5, 7) , partition
1 2 3 4

6 7 8

70
Quick-Sort(A, 0, 7)
Quick-Sort(A, 6, 7) , partition
1 2 3 4

7 88

71
Quick-Sort(A, 0, 7)
returncase
Quick-Sort(A, 7, 7) , base
1 2 3 4

7 8

72
Quick-Sort(A, 0, 7)
Quick-Sort(A, 6, 7) , return
1 2 3 4

6 7 8

73
Quick-Sort(A, 0, 7)
Quick-Sort(A, 5, 7) , return
1 2 3 4

5 6 7 8

74
Quick-Sort(A, 0, 7)
Quick-Sort(A, 4, 7) , return
1 2 3 4 5 6 7 8

75
Quick-Sort(A, 0, 7)
Quick-Sort(A, 0, 7) , done!
1 2 3 4 5 6 7 8

76
Quick-Sort: Best Case
 Even Partition
n cn

n/2 n/2 2 × cn/2 = cn

log n levels
n/4 n/4 n/4 n/4 4 × c/4 = cn

n/3 × 3c = cn
3 3 3

Total time: (nlogn)


77
Quick-Sort: Worst Case
 Unbalanced Partition
n cn

n-1 c(n-1)

n-2 c(n-2)

3c
3
Happens only if
 input is sortd
2 2c
 input is reversely sorted
Total time: (n2)

78
Quick-Sort: an Average Case
 Suppose the split is 1/10 : 9/10
n cn

0.1n 0.9n cn

log10n 0.01n 0.09n 0.09n 0.81n


cn

log10/9n
2
≤cn

2 ≤cn
Total time: (nlogn) 79
Quick-Sort Summary
 Time
 Most of the work done in partitioning.
 Average case takes (n log(n)) time.
 Worst case takes (n2) time
Space
 Sorts in-place, i.e., does not require additional
space

80
Summary
 Divide and Conquer
 Merge-Sort
 Most of the work done in Merging
 (n log(n)) time
 (n) space

 Quick-Sort
 Most of the work done in partitioning
 Average case takes (n log(n)) time
 Worst case takes (n2) time
 (1) space
81
Homework
1. What is the running time of Merge-Sort if the
array is already sorted? What is the best
case running time of Merge-Sort?

2. Demonstrate the working of Partition on


sequence (13, 5, 14, 11, 16, 12, 1, 15). What is
the value of i returned at the completion of
Partition?

82

You might also like