Scribd
Upload
3 views46 pages

Mergesort Algorithm Explained

The document describes the mergesort algorithm which works by: 1) Dividing the unsorted array repeatedly in half until each sub-array contains a single element. 2) Merging the sub-arrays together in sorted order by comparing elements and inserting the smaller element first into a new array. 3) Repeating the merge step until a fully sorted array is produced.

Uploaded by

vikram
Copyright
© All Rights Reserved
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
3 views46 pages

Mergesort Algorithm Explained

The document describes the mergesort algorithm which works by: 1) Dividing the unsorted array repeatedly in half until each sub-array contains a single element. 2) Merging the sub-arrays together in sorted order by comparing elements and inserting the smaller element first into a new array. 3) Repeating the merge step until a fully sorted array is produced.

Uploaded by

vikram
Copyright
© All Rights Reserved
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

LB

Algorithm
Mergesort(Passed an array)
if array size > 1
Divide array in half
Call Mergesort on first half.
Call Mergesort on second half.
Merge two halves.
Merge(Passed two arrays)
Compare leading element in each array
Select lower and place in new array.
(If one input array is empty then place
remainder of other array in output array)

98 23 45 14

6 67 33 42

98 23 45 14
98 23 45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23

45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

Merge

45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23
Merge

45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98
Merge

45 14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

45 14
45

14

23 98
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98
Merge

6 67 33 42
6 67 33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67
6

67

33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

6 67 33 42
6 67 33 42
6 67
6

67

14 45

14 23 45 98

Merge

33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67
6

67

6
Merge

33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67
6

67

6 67
Merge

33 42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

42

6 67
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

14 23 45 98
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

6
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

6 33
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

6 33 42
Merge

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

6 33 42 67
Merge

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98

Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98
6
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

6 67 33 42

45 14
45

23 98

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98
6 14
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98
6 14 23
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98
6 14 23 33
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98
6 14 23 33 42
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98

6 14 23 33 42 45
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98

6 14 23 33 42 45 67
Merge

42

98 23 45 14

6 67 33 42

98 23 45 14
98 23
98

23

23 98

6 67 33 42

45 14
45

14

6 67

33 42

33

14 45

67

6 67

33 42

6 33 42 67

14 23 45 98

6 14 23 33 42 45 67 98
Merge

42

98 23 45 14
98 23 45 14
98 23
98

23

23 98

45 14
45

14

14 45

14 23 45 98

6 67 33 42
6 67 33 42
6 67

33 42

33

67

6 67

42

33 42

6 33 42 67

6 14 23 33 42 45 67 98

98 23 45 14

6 67 33 42

6 14 23 33 42 45 67 98

Summary
Divide the unsorted collection into two
Until the sub-arrays only contain one
element
Then merge the sub-problem solutions
together

Questions?

Review?

You might also like