RICORSIONE: DEFINIZIONI RICORSIVERICORSIONE: DEFINIZIONI RICORSIVE

Definizione ricorsiva: Definizione ricorsiva: definizione di una classe di “oggetti” in termini di una sottoclasse degli “oggetti” stessi.

Consiste di due fasi1) BASE. Si definiscono uno o più “oggetti”2) PASSO Induttivo. Si definiscono altri “oggetti”

a partire da quelli già definiti.Es. n fattoriale: n!=1x2x…xn= prodotto dei primi n interiDefinizione ricorsiva di n fattoriale, f(n):BASE. f(1)=1PASSO. f(n)=f(n-1)Xn, per n>1

Applicando successivamente il passo induttivo a partire da f(1) otteniamo:f(2)=f(1)x2=2, f(3)=f(2)x3=2x3=6, f(4)=f(3)x4=6x4=24,…

Definizione ricorsiva di n fattoriale, f(n):BASE. f(1)=1PASSO. f(n)=f(n-1)Xn

Mostriamo che la definizione data è corretta, cioè consideriamo la seguente affermazione

S(n): f(n)=n!e dimostriamo che S(n) vera per ogni n>1.

Definizione ricorsiva di n fattoriale, f(n):BASE. f(1)=1PASSO. f(n)=f(n-1)Xn

Mostriamo che la definizione data è corretta, cioè consideriamo la seguente affermazione

S(n): f(n)=n!e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.BASE. n=1. Si ha f(n)=1=1! S(1) vera

Definizione ricorsiva di n fattoriale, f(n):BASE. f(1)=1PASSO. f(n)=f(n-1)Xn

Mostriamo che la definizione data è corretta, cioè consideriamo la seguente affermazione

S(n): f(n)=n!e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.BASE. n=1. Si ha f(n)=1=1! S(1) vera

PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!). Vogliamo mostrare che S(n+1) è vera.

Definizione ricorsiva di n fattoriale, f(n):BASE. f(1)=1PASSO. f(n)=f(n-1)Xn

Mostriamo che la definizione data è corretta, cioè consideriamo la seguente affermazione

S(n): f(n)=n!e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.BASE. n=1. Si ha f(n)=1=1! S(1) vera

PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!). Vogliamo mostrare che S(n+1) è vera. Si ha

f(n+1)=f(n)x(n+1)=n!x(n+1) (per i.i.) =(1x…xn)x(n+1)=1x…x(n+1)= (n+1)!

Quindi S(n+1) è vera.

Definizione ricorsiva dell’ordine lessicograficoDefinizione ricorsiva dell’ordine lessicografico

Definiamo in modo ricorsivo coppie di stringhe W Definiamo in modo ricorsivo coppie di stringhe W ed X tali cheed X tali che

W<X

Indichiamo con la stringa vuota.

BASE. 1. <W, per ogni stringa W non vuota 2. se c<d (c,d caratteri) allora per ogni coppia di stringhe W,X risulta

cW<dXPASSO. Date le stringhe W ed X, se W<X allora per c ogni carattere c risulta

cW<cX

Definizione ricorsiva dell’ordine lessicograficoDefinizione ricorsiva dell’ordine lessicografico

BASE. 1. <W, per ogni W non vuota 2. se c<d cW<dX, per ogni W,X PASSO. W<X cW<cX, per ogni carattere c

Esercizio. Mostrare che se X<Y secondo la definizione ricorsiva data, allora X precede Y in ordine lessicografico. [Suggerimento: procedere per induzione sulla lunghezza del prefisso comune alle due stringhe]

Ricorda: Ordine lessicografico Data una coppia di sequenze c1c2 …ck, d1d2…dm risulta

c1c2 …ck < d1d2…dm

1) se k<m e c1=d1,…,ck=dk (la prima è l’inizio della seconda) 2) oppure c1=d1,..,ci-1=di-1, ci<di per qualche i. (ordine dato dal primo simbolo in cui le due sequenze differiscono)

Definizione ricorsiva dell’ordine lessicograficoDefinizione ricorsiva dell’ordine lessicografico

BASE. 1. <W, per ogni W non vuota 2. se c<d cW<dX, per ogni W,X PASSO. W<X cW<cX, per ogni carattere c

Esercizio. Mostrare che se X<Y secondo la definizione ricorsiva data, allora X precede Y in ordine lessicografico. [Suggerimento: procedere per induzione sulla lunghezza del prefisso comune alle due stringhe]Affermazione S(n): Date due stringhe X,Y con prefisso comune lungo n, se X<Y allora X precede Y in ordine lessicografico

Si vuole provare che S(n) vera per ogni n>0.

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Es. (y*(-(x+9)) è una espressione aritmetica.

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Es. (y*(-(x+9)) è una espressione arirmetica.

Verifica: Usando la BASE: x,y e 9 sono espressioni aritmetiche

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Es. (y*(-(x+9)) è una espressione arirmetica.

Verifica: Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Es. (y*(-(x+9)) è una espressione arirmetica.

Verifica: Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.Usando il PASSO: (x+9) è e.a. (-(x+9)) è e.a.

Definizione ricorsiva di espressioni aritmeticheDefinizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni aritmetichePASSO. Se E1 ed E2 sono espressioni aritmetiche allora

(E1+E2), (E1-E2), (E1*E2), (E1/E2), (-E1) sono espressioni aritmetiche.

Es. (y*(-(x+9))) è una espressione arirmetica.

Verifica: Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.Usando il PASSO: (x+9) è e.a. (-(x+9)) è e.a.

Usando il PASSO: y e (-(x+9)) e.a. (y*(-(x+9))) è e.a.

FUNZIONI RICORSIVEFUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input diverso).

FUNZIONI RICORSIVEFUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input diverso).

Funzioni ricorsive Definizioni ricorsive

Es. Calcolo di n! usando la definizione ricorsiva di fattoriale.

Base. 1!=1 Passo. n!= (n-1)! X n

FUNZIONI RICORSIVEFUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input diverso).

Funzioni ricorsive Definizioni ricorsive

Es. Calcolo di n! usando la definizione ricorsiva di fattoriale.

Base. 1!=1 Passo. n!= (n-1)! X n

Int fact(int n){ if(n<=1) return 1 /*Base*/ else return n*fact(n-1); /*Passo*/}

Int fact(int n){ if(n<=1) return 1 /*Base*/ else return n*fact(n-1); /*Passo*/}

n=1: fact(1) termina e restituisce 1!=1

Int fact(int n){ if(n<=1) return 1 /*Base*/ else return n*fact(n-1); /*Passo*/}

n=1: fact(1) termina e restituisce 1!=1

chiaman=2: fact(2) fact(1) 1

Int fact(int n){ if(n<=1) return 1 /*Base*/ else return n*fact(n-1); /*Passo*/}

n=1: fact(1) termina e restituisce 1!=1

chiaman=2: fact(2) fact(1) 1

chiama chiama n=3: fact(3) fact(2) fact(1) 2 1

Int fact(int n){ if(n<=1) return 1 /*Base*/ else return n*fact(n-1); /*Passo*/}

n=1: fact(1) termina e restituisce 1!=1

chiaman=2: fact(2) fact(1) 1

chiama chiama n=3: fact(3) fact(2) fact(1) 2 1

chiama chiama chiama

n: fact(n) fact(n-1) … fact(1) (n-1)! (n-2)! 1

SelectionSort RICORSIVOSelectionSort RICORSIVO

Idea alla base del SelectionSort: Array A diviso in due parti

A[0..i-1] ordinato A[i..n-1] elementi più grandi da

ordinare 1. Trova min A[i..n-1], sia A[small] Scambia A[i] ed A[small]2. Ordina la parte non ordinata, cioè A[i+1..n-

1]

SelectionSort RICORSIVOSelectionSort RICORSIVO

Idea alla base del SelectionSort: Array A diviso in due parti

A[0..i-1] ordinato A[i..n-1] elementi più grandi da

ordinare 1. Trova min A[i..n-1], sia A[small] Scambia A[i] ed A[small]2. Ordina la parte non ordinata, cioè A[i+1..n-

1]BASE. Se i=n-1, la parte da ordinare è A[n-1], ok.PASSO. Se i<n-1, trova min A[i..n-1], scambialo con A[i]; ordina (ricorsivamente) A[i+1..n-1]

SelectionSort RICORSIVOSelectionSort RICORSIVO

void Rec- SelectionSort(int A[], int i, int n)int j,small,temp;{ if (i<n-1) /* Base: i=n-1, Esci*/ { /*Esegui Passo*/

small=i;for(j=i+1, j<n,j++) if (A[j]<A[small])

small=j; /*trova min*/

temp=A[small]; A[small]=A[i]; A[i]=temp; /*scambia*/

Rec-SelectionSort(A,i+1,n) }}

BASE. Se i=n-1, la parte da ordinare è A[n-1], ok.PASSO. Se i<n-1, trova min A[i..n-1], scambialo con A[i]; ordina (ricorsivamente) A[i+1..n-1]

Numeri di FIBONACCINumeri di FIBONACCI

BASE. fib(0)=fib(1)=1;PASSO. fib(n)=fib(n-1)+fib(n-2)

Numeri di FIBONACCINumeri di FIBONACCI

BASE. fib(0)=fib(1)=1;PASSO. fib(n)=fib(n-1)+fib(n-2)

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

n=0, oppure n=1: restituisce 1

Fib(1) n=2: Fib(2)

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

n=0, oppure n=1: restituisce 1

Fib(1) n=2: Fib(2) Fib(0)

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

n=0, oppure n=1: restituisce 1

Fib(1) n=2: Fib(2) Fib(0)

Fib(1) Fib(2)

n=3: Fib(3) Fib(0)

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

n=0, oppure n=1: restituisce 1

Fib(1) n=2: Fib(2) Fib(0)

Fib(1) Fib(2)

n=3: Fib(3) Fib(0) Fib(1)

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Fib(1) Fib(2)

n=3: Fib(3) Fib(0) Fib(1)

Fib(1) Fib(2)

Fib(3) Fib(0) n=4: Fib(4) Fib(1)

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (i<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Fib(1) Fib(2)

n=3: Fib(3) Fib(0) Fib(1)

Fib(1) Fib(2)

Fib(3) Fib(0) n=4: Fib(4) Fib(1)

Fib(1) Fib(2)

Fib(0)

INDUZIONE COMPLETAINDUZIONE COMPLETA

Vogliamo dimostrare che S(n) vale per ogni intero n>a.

Dimostrazione per induzione completa:

1. BASE INDUTTIVA. Si dimostra che l’affermazione è vera per il primo valore, cioè S(a) è vera.

2. PASSO INDUTTIVO. Assumiamo che S(a), S(a+1),…, S(n-1) sono tutte vere e dimostriamo che anche S(n) è

vera.

VALIDITA’ delle dim. per INDUZIONE Completa VALIDITA’ delle dim. per INDUZIONE Completa

Dim. per induzione S(n) vera, ogni n>a

Base: S(a) vera

Passo induttivo

Minimo controesempio. Supponiamo S(n) falsa per qualche n.Sia b il più piccolo intero tale che S(b) falsa.DEDUCIAMO: Se b=a contraddiciamo la base. Quindi b>a. Essendo b-1>a e b = minimo intero per cui l’affermazione è falsa, si ha S(a),…, S(b-1) vere Per il Passo Induttivo, se S(a),…,S(b-1) sono vere allora anche S(b) è vera.

Abbiamo una contraddizione con l’assunzione che S(b) falsa. Quindi ipotesi è sbagliata enon esiste intero per cui l’affermazione è falsa.

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (n<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione S(n): il numero di chiamate fatte per calcolare Fib(n)

è maggiore di fib(n).Per ogni n > 2

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (n<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione S(n): il numero di chiamate fatte per calcolare Fib(n) è maggiore di fib(n).Per ogni n > 2

1. BASE INDUTTIVA. S(2) è vera.2. PASSO Ind. S(2), …, S(n-1) implicano S(n)

vera.

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (n<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione S(n): il numero di chiamate fatte per

calcolare Fib(n) è maggiore di fib(n).Per ogni n>1.

BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) è vera.

Numeri di FIBONACCINumeri di FIBONACCI

int Fib (int n){ if (n<=1) return 1 /* Base*/ else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione S(n): il numero di chiamate (ricorsive) fatte per

calcolare Fib(n) è maggiore di fib(n).Per ogni n>1.

BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) vera.

PASSO. Assumiamo S(2), …, S(n-1) vere. Il numero di chiamate fatte per calcolare

Fib(n) è 1+(numero chiamate per Fib(n-1)) +(numero chiamate per Fib(n-2))> (per

i.i.) 1+fib(n-1)+fib(n-2)=1+fib(n)>fib(n)Quindi S(n) vera.

Numeri di FIBONACCINumeri di FIBONACCI

Esercizio.Mostrare per induzione completa l’affermazione

S(n):

Per ogni n>5.

n

nfib

2

3)(

BASE. fib(0)=fib(1)=1;PASSO. fib(n)=fib(n-1)+fib(n-2)

Numeri di FIBONACCINumeri di FIBONACCI

Esercizio.

Scrivere un programma iterativo per il calcolo di fib(n).

Nota: è sufficiente un ciclo iterativo (con n iterazioni)

BASE. fib(0)=fib(1)=1;PASSO. fib(n)=fib(n-1)+fib(n-2)

Sorting: MERGESORTSorting: MERGESORT

Vogliamo ordinare lista (a1,…,an).

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a1,a3,a5,…) e (a2,a4,…)2. Ordina le due liste separatamente3. Fai “merge” delle due lista ottenute (ordinate)

in una unica lista ordinata

Sorting: MERGESORTSorting: MERGESORT

Esempio di una tecnica generale: “Divide and Conquer”

Sottoproblema 1 (simile, più semplice)

Sottoproblema 2

Problema ……

Sottoproblema n Ogni sottoproblema risolto con la stessa tecnica. Finchè non si raggiunge un sottopr. risolvibile direttamente.

Sorting: MERGESORTSorting: MERGESORT

Esempio di una tecnica generale: “Divide and Conquer”

Sottoproblema 1 (simile, più semplice)

Sottoproblema 2

Problema ……

Sottoproblema n Ogni sottoproblema risolto con la stessa tecnica. Finchè non si raggiunge un sottopr. risolvibile direttamente.

soluzione Sottoproblema 1 soluzione Sottoproblema 2

soluzione Problema

… … soluzione Sottoproblema n

Sorting: MERGESORTSorting: MERGESORT

Vogliamo ordinare lista (a1,…,an).

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a1,a3,a5,…) e (a2,a4,…)2. Ordina le due liste separatamente3. Fai “merge” delle due lista ottenute (ordinate)

in una unica lista ordinata

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

Es. L1=(1,2,7,7,9), L2=(2,4,7,8)

M=(1,2,2,4,7,7,7,8,9)

- Trova il minimo tra il primo elemento di L1 e di L2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L1=(1,2,7,7,9), L2=(2,4,7,8), M=(), minimo=1 in L1

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

Es. L1=(1,2,7,7,9), L2=(2,4,7,8)

M=(1,2,2,4,7,7,7,8,9)

- Trova il minimo tra il primo elemento di L1 e di L2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L1=(1,2,7,7,9), L2=(2,4,7,8), M=(), minimo=1 in L1

L1=(2,7,7,9), L2=(2,4,7,8), M=(1), minimo=2

in L1

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

Es. L1=(1,2,7,7,9), L2=(2,4,7,8)

M=(1,2,2,4,7,7,7,8,9)

- Trova il minimo tra il primo elemento di L1 e di L2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L1=(1,2,7,7,9), L2=(2,4,7,8), M=(), minimo=1 in L1

L1=(2,7,7,9), L2=(2,4,7,8), M=(1), minimo=2

in L1

L1=(7,7,9), L2=(2,4,7,8), M=(1,2), minimo=2 in L2

MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)

L1=(1,2,7,7,9), L2=(2,4,7,8), M=(), minimo=1 in L1

L1=(2,7,7,9), L2=(2,4,7,8), M=(1), minimo=2

in L1

L1=(7,7,9), L2=(2,4,7,8), M=(1,2), minimo=2 in L2

L1=(7,7,9), L2=(4,7,8), M=(1,2,2), minimo=4 in L2

L1=(7,7,9), L2=(7,8), M=(1,2,2,4), minimo=7 in L1

L1=(7,9), L2=(7,8), M=(1,2,2,4,7), minimo=7 in L1

L1=(9), L2=(7,8), M=(1,2,2,4,7,7), minimo=7 in L2

L1=(9), L2=(8), M=(1,2,2,4,7,7,7), minimo=8 in L1

L1=(9), L2=(), M=(1,2,2,4,7,7,7,8), L2 vuota

Aggiungi L2 ad M.M= =(1,2,2,4,7,7,7,8,9).

MERGESORTMERGESORT

BASE: Se la lista contiene 0 o 1 elemento, stop Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…) Mergesort delle due liste separatamente Merge delle 2 liste ordinate

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

7-1 9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

7-1 9

7 1

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

7-1

7 1

7 1

1-7

9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

7-1 9

7 1

7 1

1-7 9

1-7-9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7

7-1 9 2 7

7 1

7 1

1-7 9 2 7

1-7-9 2-7

1-2-7-7-9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7 8-24-7

7-1 9 2 7

7 1

7 1

1-7 9 2 7

1-7-9 2-7

1-2-7-7-9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7 8-24-7

7-1 9 2 7 4 7

7 1

7 1

1-7 9 2 7 4 7

1-7-9 2-7 4-7

1-2-7-7-9

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7 8-24-7

7-1 9 2 7 4 7 8 2

7 1

7 1

1-7 9 2 7 4 7 8 2

1-7-9 2-7 2-84-7

1-2-7-7-9 2-4-8-7

MERGESORTMERGESORT7-4-2-8-9-7-7-2-1

7-2-9-7-1 4-8-7-2

7-9-1 2-7 8-24-7

7-1 9 2 7 4 7 8 2

7 1

7 1

1-7 9 2 7 4 7 8 2

1-7-9 2-7 2-84-7

1-2-7-7-9 2-4-7-8

1-2-2-4-7-7-7-8-9