Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

7
...
In this technique, the complete list is divided into
sublists and each sublist is having one element
...

• Example
• Let's take an example to understand how merge sort works
...
We divide the
list into two equal subarrays, and each sublist is further divided into
two halves until we get sublists with only one element
...


•

Merge Sort Algorithm Code

void mergeSort(int arr[], int l, int r) {

•

< r)

{

int m = l+(r-l)/2;

mergeSort(arr, l, m);
r);
•

if (l

mergeSort(arr, m+1,

merge(arr, l, m, r);

}}

The backbone of the merge sort algorithm is the merge function that
merges the subarrays
...
Then,
the sorted sublists are merged to form a new sorted list
...


•

The recursive tree for the given example is shown below:
•

0-8

•

0-4
•

0-2
•

0-1
•

•

•

2

•

5-6

1

•

5

•

6

•

7

•

8

5-8

•

•

•

0

7-8

The merging of sorted sublists is done as follows:

1
...

2
...

3
...

4
...

5
...




---