Scribd
Upload
16 views7 pages

Merge Sort

The document discusses sorting algorithms, particularly focusing on the Divide-and-Conquer method exemplified by Merge Sort. It outlines the steps involved in sorting a sequence of elements, including dividing the sequence, recursively sorting the subsequences, and merging them to achieve a sorted result. Additionally, it compares the running times of Insertion Sort and Merge Sort, highlighting their efficiency and memory requirements.

Uploaded by

iamnityasinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views7 pages

Merge Sort

The document discusses sorting algorithms, particularly focusing on the Divide-and-Conquer method exemplified by Merge Sort. It outlines the steps involved in sorting a sequence of elements, including dividing the sequence, recursively sorting the subsequences, and merging them to achieve a sorted result. Additionally, it compares the running times of Insertion Sort and Merge Sort, highlighting their efficiency and memory requirements.

Uploaded by

iamnityasinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting

Sorting

• Given a set (container) of n elements


E.g. array, set of words, etc.
• Suppose there is an order relation that can be set
across the elements
• Goal : Arrange the elements in ascending order

Start 🡪 1 23 2 56 9 8 10 100
End 🡪 1 2 8 9 10 23 56 100
Divide-and-Conquer

• Divide and Conquer is a method of algorithm design that has


created such efficient algorithms as Merge Sort.
• In terms or algorithms, this method has three distinct steps:
Divide: If the input size is too large to deal with in a
straightforward manner, divide the data into two or more
disjoint subsets.
Recur: Use divide and conquer to solve the subproblems
associated with the data subsets.
Conquer: Take the solutions to the subproblems and “merge”
these solutions into a solution for the original problem.
An Example: Merge Sort
Sorting Problem: Sort a sequence of n elements into
non-decreasing order.

• Divide: Divide the n-element sequence to be sorted into


two subsequences of n/2 elements each

• Conquer: Sort the two subsequences recursively using


merge sort.

• Combine: Merge the two sorted subsequences to produce


the sorted answer.
Merge Sort – Example
18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2
Merge Sort – Example
Original Sorted
18 26
Sequence
32 6 43 15 9 1 Sequence
1 6 9 15 18 26 32 43

18 26 32 6 43 15 9 1 6 18 26 32 1 9 15 43
43

18 26 32 6 43 15 9 1 18 26 6 32 15 43 1 9

18 26 32 6 43 15 9 1 18 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1
Sorting Algorithms so far

• Insertion sort
Worst-case running time Q(n2)

• Merge sort
Worst-case running time Q(n log n), but requires
additional memory Q(n);

You might also like