Sorting: MERGESORT
Vogliamo ordinare lista (a1,…,an).
1. Dividi lista in 2 sottoliste aventi (quasi) la stessa
dimensione: (a1,a3,a5,…) e (a2,a4,…), (SPLIT)
2. Ordina le due liste separatamente (MERGESORT)
3. Fondi le due liste ottenute (ordinate) in una
unica lista ordinata (MERGE)
MERGE (di due liste ordinate L1,L2  M)
Algoritmo dipende dalla rappresentazione delle liste
Usiamo LISTE A PUNTATORI:
ogni elemento della lista è una struttura
typedef struct CELL *LIST
struct CELL{
int element
/* elemento della lista*/
LIST next
/* puntatore alla successiva
struttura (elemento)*/
}
(a1,a2,…,an) 
a1
a2
…
an
MERGE (di due liste ordinate L1,L2  M)
-Trova il minimo tra il primo elemento di L1 e di L2,
rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
Ripeti
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
-
}
else
if (list1->element <= list2 -> element)
/* entrambe le liste non vuote ed il primo
elemento di list1 è minore del primo di list2*/
{ list1->next=merge(list1->next, list2);
return list1;
}
else /*entrambe le liste non vuote ed il primo
elemento di list2 è minore del primo di list1*/
{ list2->next=merge(list1, list2->next);
return list2;
}
MERGE (di due liste ordinate L1,L2  M)
-Trova il minimo tra il primo elemento di L1 e di L2,
rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
Ripeti
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
-
}
else
if (list1->element <= list2->element)
/* entrambe le liste non vuote ed il primo
elemento di list1 è minore del primo di list2*/
{ list1->next=merge(list1->next, list2);
return list1;
}
else /*entrambe le liste non vuote ed il primo
elemento di list2 è minore del primo di list1*/
{ list2->next=merge(list1, list2->next);
return list2;
}
MERGE (di due liste ordinate L1,L2  M)
-Trova il minimo tra il primo elemento di L1 e di L2,
rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
Ripeti
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
-
}
else /* entrambe le liste non vuote*/
if (list1->element <= list2->element)
/* entrambe le liste non vuote ed il primo
elemento di list1 è minore del primo di list2*/
{ list1->next=merge(list1->next, list2);
return list1;
}
else /*entrambe le liste non vuote ed il primo
elemento di list2 è minore del primo di list1*/
{ list2->next=merge(list1, list2->next);
return list2;
}
MERGE (di due liste ordinate L1,L2  M)
LIST merge (LIST list1, LIST list2) {
if (list1==NULL) return list2
else if (list2==NULL) return list1
else if ( list1->element <= list2->element )
{/* entrambe le liste non vuote ed il primo elemento
di list1 è minore del primo di list2*/
list1->next=merge(list1->next, list2);
return list1;}
else
…}
list1
a1
a2
list2
b1
b2
list1
a1
merge
an
…
…
a2
b1
bn
…
…
an
bn
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
list1=merge(list1, list2)  merge (2-4-7, 3-5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
g= merge(g, b)
 merge(4-7, 5-6-9)

merge(7, 5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e)

merge(7, 9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e)
t= merge(NULL, e)=e

merge(7, 9)

merge( , 9)
e
9
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e) =g

merge(7, 9)
g
7
t
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
g= merge(g, b)
d= merge(g, d)=d
 merge(4-7, 5-6-9)

merge(7, 5-6-9)

merge(7, 6-9)
d
6
e
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
g= merge(g, b) = b
 merge(4-7, 5-6-9)
 merge(7, 5-6-9)
b
5
d
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b) = a

merge(4-7, 5-6-9)
a
4
g
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
list1=merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)=list2  merge(4-7,3-5-6-9) list2
3
b
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
list1=merge(list1, list2)  merge (2-4-7, 3-5-6-9) list1
9 p
2
a
SPLIT (di L in due liste ordinate L1,L2)
L=(a1,a2, a3, a4, …, an)  L1 =(a1, a3, …) , L2 =(a2, a4, …)
LIST Split (LIST list)
{
List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else
{/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;
}
}
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
pSecondcell
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
pSecondcell
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
a1
a2
a3
Split di
pSecondcell
…
an
MERGESORT
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
MERGESORT
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
LIST Mergesort (LIST list)
{
List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else
{/* list contiene almeno 2 elementi (da ordinare)*/
SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));
}
}
R.T. della funzione SPLIT
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
Sia n=|list|. Si ha la relazione di ricorrenza
T(0)=T(1)=O(1)
T(n)=c+T(n-2), per n>1
Quindi T(n)=O(n)
R.T. del MERGE
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
}
else
if (list1->element <= list2 -> element)
{ list1->next=merge(list1->next, list2);
return list1; }
else
{ list2->next=merge(list1, list2->next);
return list2;}
Siano n1=|list1|, n2=|list2|, n=n1+n2.
Si ha la relazione di ricorrenza
T(0)=T(1)=O(1) (almeno 1 lista vuota)
T(n)=c+T(n-1), per n>1
Quindi T(n)=O(n)
R.T. MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Sia n=|list|. Si ha la relazione di ricorrenza
T(0)=T(1)=O(1) (list contiene 0 o 1 elemento)
T(n)=O(n) + O(n) +T(n/2) +T(n/2)
=O(n) + 2 T(n/2), per n>1
Quindi T(n)=O(n log n)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
T(2m)=c 2m + 2 T(2m-1)
=c 2m + 2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4 T(2m-2)
= 2c 2m + 4 T(2m-2)
= 2c 2m +4 (c 2m-2 + 2 T(2m-3))=2c 2m + c 2m+8T(2m-3)
= 3c 2m + 8 T(2m-3)
……
= i c 2m + 2i T(2m-i)
Scegliendo i=m=log n si ha
T(n)= T(2m) = m c 2m + 2m T(20)= m c n + n a=
= c n log n + a n = O(n log n)
Correttezza MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Assumiamo correttezza delle funz.split e merge (esercizio)
Per induzione completa su n=|list|.
Base. Se n=0 o n=1, restituisce lista inalterata, ok.
Passo (n>1). Assumiamo per i.i. mergesort(list),
mergesort(ScondList) restituiscono liste input ordinate.
Quindi Split divide gli elementi lista input con n elementi tra
list e Secondlist; mergesort(list),mergesort(ScondList)
ordina le liste;
Merge fonde le liste restituendo in output una lista ordinata
contenete gli stessi n elementi della lista input.