DS8 MERGESORT

Question 1

MERGE SORT INTRO

Answer 1

can be stable
serial accessing data
for high efficiency fast data access systems/computers

Question 2

TOP-DOWN MERGE SORT (1)

Answer 2

2 recursive calls to files with half original size
recursion stops when file has only 1 element
uses merge to combine the 2 sub-arrays

static void mergesort(itam[] a, int p, int r){
~if(r <= p){return;}
~int m = r+p/2;
~mergesort(a, p, m);
~mergesorst(a, m+1, r);
~merge(a, p, m, r);
}
divide and conquer trees are a visual representation of mergesort

Question 3

MERGE METHOD (1)

Answer 3

• 2 sorted arrays a, b
• 1 sorted array c

find least in a, b
copy to c in correct order
update pointers
if a is ap, ar and b is bp, br then c is
p + (ar-ap + 1)+(br-bp+1)
p is assuming we start from a specific place in array c

static void mergeAB(item[] out, int p, item[] a, int ap, int ar, item[] b, int bp, int br){
int i = ap, j = bp;
for (int k = p; k < p+ar-ap+br-bp+2; k ++){
if(i>ar){out[k] = b[j++]; continue;}
if (j> br){out[k] = a[i++]; continue;}
out[k] = less(a[i], b[j])? a[i++]:b[j++];)
// means if a[i] is less i++ if b is less j++//
}}

Question 4

ABSTRACT DIRECT MERGE SORT (2)

Answer 4

merge in input array
sub arrays are also in input array we know at which index they are seperated
a is p to m
b is m+1 to r
avoid termination checks
reverse second array largest items are next to each other
the largest of the 2 is guard
uses auxiliary array

static void merge(item[] a, int p, int m, int r){
int i, j;
//first iter m last iter p first item in aux is p and last is m
for (i = m+1; i>p; i–){aux[i-1] = a[i-1];}
// first iter m+1 last iter r first item in aux is r and last is m+1
for(j =m; j<r; j++){aux[j+1] = a[r +m-j];}
for(int k = p; k<= r; k++){
if(less(aux[j], aux[i]a)){a[k] = aux[j–];}
else{a[k] = aux[i++];}
}}
n=r-p+1
O(nlogn) complexity
but O(n) extra space
can become stable with double keys

Question 5

BOTTOM UP MERGE SORT (3)