[̲] [] [] [ ]

 

8.2.2.

 

, , , . . . ( ) .

2 . f1. f2 f3, f1. f2, f3, - f2 . ϳ f2 f3 f1. f2 f3, .. , . ϳ f1 f2 f3, . , f1 .

, , :

 

t =

key: t;

p: s

;

fl = t;

 

s , t : {=, <>, <, >, >=, <=}. key. C, A B. :

 

(C);

Ø eof(C)

C A B;

A B n C;

n=1

 

ij C A B Divide. x , y , ToA , (A B).

 

Divide( C, A, B: fl) ;

x,y: t;

ToA: boolean;

(C); (A); (B);

{ C , }

(C,x);

ToA <- ;

Øeof(C)

ToA (A,x)

(B,x) ;

(C,y);

y.key < x.key { }

ToA := ØToA

;

x <- y

;

{ C}

{ A B}

ToA (A,x)

(B,x) ;

(C); (A); (B);

;

 

ij A B n C Merge3. x C ; y , C; xa A; xb B; EndOfA, EndOfB , , (A B) , C; FromA , , C. , A :

1)    B C;

2)    B B C ( );

3)    C, B C.

C .

 

Merge3( A, B, C: fl; n: )

xa,xb,x,y: t;

EndOfA, EndOfB, FromA: ;

(A); (B); (C);

n <- 1;

{ A }

EndOfA <- ;

(A,xa); x <- xa;

EndOfB <- eof(B);

ØEndOfB

(B,xb);

xb.key<xa.key x <- xb ;

;

{ A B C}

ØEndOfA Ú ØEndOfB

EndOfA FromA <-

EndOfB FromA <-

FromA <- xa.key<=xb.key & xa.key>=x.key Ú

xa.key<=xb.key & xb.key<x.key Ú

xa.key>=x.key & xb.key<x.key;

;

FromA

y <- xa;

Øeof(A) (A,xa)

EndOfA <- ;

y <- xb;

Øeof(B) (B,xb)

EndOfB <- ;

;

y.key < x.key n <- n+1 ;

(C,y);

x <- y

;

(C); (A); (B);

;

 

:

 

NaturalMerge3

 

t =

key: t;

p: s

;

fl = t;

 

Divide( C, A, B: fl) ;

x,y: t;

ToA: boolean;

(C); (A); (B);

(C,x);

ToA <- ;

Øeof(C)

ToA (A,x)

(B,x) ;

(C,y);

y.key < x.key

ToA := ØToA

;

x <- y

;

ToA (A,x)

(B,x) ;

(C); (A); (B);

;

 

Merge3( A, B, C: fl; n: )

xa,xb,x,y: t;

EndOfA, EndOfB, FromA: ;

(A); (B); (C);

n <- 1;

EndOfA <- ;

(A,xa); x <- xa;

EndOfB <- eof(B);

ØEndOfB

(B,xb);

xb.key<xa.key x <- xb ;

;

ØEndOfA Ú ØEndOfB

EndOfA FromA <-

EndOfB FromA <-

FromA <- xa.key<=xb.key & xa.key>=x.key Ú

xa.key<=xb.key & xb.key<x.key Ú

xa.key>=x.key & xb.key<x.key;

;

FromA

y <- xa;

Øeof(A) (A,xa)

EndOfA <- ;

y <- xb;

Øeof(B) (B,xb)

EndOfB <- ;

;

y.key < x.key n <- n+1 ;

(C,y);

x <- y

;

(C); (A); (B);

;

 

n: ;

(C);

Ø eof(C)

Divide(C, A, B);

Merge3(A, B, C, n);

n=1

.

 

( ):

 

C 23 55|47|35|10 90|84|30

i=1

A 23 55|35 84

B 47|10 90|30

n=3

C 23 47 55|10 35 84 90|30

i=2

A 23 47 55|30

B 10 35 84 90

n=2

C 10 23 35 47 55 84 90|30

i=3

A 10 23 35 47 55 84 90

B 30

n=1

C 10 23 30 35 47 55 84 90

 

i ... .

 

2 , , , . . , , ( - ). f1. f4 f1, f4 f2 f3. f2, f3, - f2 . ϳ f2 f3 f1 f4 .. , f1 . , , C, A, B D. :

 

(C); (D);

Ø eof(C)

C D n A B;

A B n C D;

n=1

 

Merge3. , : , . . :

 

NaturalMerge4

 

t =

key: t;

p: s

;

fl = t;

 

Merge4( A, B, C, D: fl; n: )

xa,xb,x,y: t;

EndOfA, EndOfB, FromA: ;

(A); (B); (C); (D);

n <- 1;

EndOfA <- ;

(A,xa); x <- xa;

EndOfB <- eof(B);

ØEndOfB

(B,xb);

xb.key<xa.key x <- xb ;

;

ØEndOfA Ú ØEndOfB

EndOfA FromA <-

EndOfB FromA <-

FromA <- xa.key<=xb.key & xa.key>=x.key Ú

xa.key<=xb.key & xb.key<x.key Ú

xa.key>=x.key & xb.key<x.key;

;

FromA

y <- xa;

Øeof(A) (A,xa)

EndOfA <- ;

y <- xb;

Øeof(B) (B,xb)

EndOfB <- ;

;

y.key < x.key n <- n+1 ;

n mod 2 = 1 (C,y)

(D,y) ;

x <- y

;

(C); (D); (A); (B);

;

 

n: ;

(C); (D);

Ø eof(C)

Merge4(C, D, A, B, n);

Merge4(A, B, C, D, n);

n=1

.

 

:

 

C 23 55|47|35|10 90|84|30

i=1

A 23 55|35 84

B 47|10 90|30

n=3

C 23 47 55|30

D 10 35 84 90

i=2

A 10 23 35 47 55 84 90

B 30

n=1

C 10 23 30 35 47 55 84 90

D

 

... .

 

, . , . . .

 

1024 4096 16384

NaturalMerge3 0.00 0.05 0.50 0.16 0.17 2.08 0.72 0.71 9.44

NaturalMerge4 0.11 0.11 0.05 0.16 0.17 0.16 0.71 0.71 0.83

 

, (NaturalMerge4) , . , , .

 

 

8.1. .

 

[̲] [] [] [ ]