Selection & Merging

Split file (divide +conquer)

Merging: sorted file +sorted file→lager sorted file

Merge file

Quick Sort: divide 2 sorted file→whole file sorted

: most done before recursive calls(Conquer &Divide)

Merge Sort: divide 2 sorted file+merge→whole file sorted

:most done after recursive calls(Divide & Conquer)

　

Merge

2-way merge:

array merge:

list merge:

T=M+N

　

i:=1; j:=1;

a[M+1]:=∞;b[N+1]:=∞;

for K:=1 to M+N do

if a[i]<b[j] then c[K]:=a[i]; i:=i+1;

else c[K]:=b[j]; j:=j+1;

　

Merge Sort

˙array

m:=(l+r) div l;

mergeSort(l+m);mergeSort(m+1,l);

copy(a,b,l,m); CopyR(a,b,m+1,r);

merge

　

˙array

　

a:= c ; b:= c.next ; b:=b.next;b:=b.next;

while b≠Z do

c:=c.next ; b:=b.next; b:=b.next;

b.c=next; c.next:=Z;

mergeSort := Merge(mergesort(a),mergesort(b));

˙Build up small sorted file into larger ones (top down)

˙

˙Example: