#!/usr/bin/perl -w

#
# merge-sort.pl
#
# Programma che legge ed ordina dei dati usando l'algoritmo merge-sort
# Input: una successione di numeri interi terminata da EOF (end of file)
# Output: i numeri ordinati
#

&main;	# eseguo il programma principale

#-------------------------------------------------------------------------
#
# Routine che fonde due liste ordinate ottenendo una terza lista ordinata
# Le due liste sono passate per riferimento altrimenti verrebbero concatenate
# alla chiamata
#

sub merge (\@\@) {
	my $lista1 = shift;	# riferimento alla prima lista
	my $lista2 = shift;	# riferimento alla seconda lista
	my @lista1 = @$lista1;	# riottengo la prima lista
	my @lista2 = @$lista2;	# riottengo la seconda lista

print "merging:\n";
print "\t" , join( " ", @lista1) , "\n";
print "\t" , join( " ", @lista2) , "\n";

	my @lista;		# lista risultante
	my ($x,$y);
	while (1) {
		# se la lista2 è finita concateno lista1 dopo quanto raccolto finora
		return (@lista, @lista1) if (!@lista2);
		# se la lista1 è finita concateno lista2 dopo quanto raccolto finora
		return (@lista, @lista2) if (!@lista1);
		# altrimenti esistono ancora valori sia in lista1 che lista2
		if ($lista1[0] < $lista2[0]) {		# confronto i primi elementi
			# se il minore è in lista1 lo estraggo e concateno al risultato
			push( @lista, shift @lista1);
		} else {
			# altrimenti il minore è in lista2, lo estraggo e concateno al risultato
			push( @lista, shift @lista2);
		}
	}
	return @lista;	# torno il risultato
}

#-------------------------------------------------------------------------
#
# mergesort di una lista
#
sub mergeSort (@) {
	my @dati = @_;			# prendo i dati
	my $quanti = $#dati + 1;	# li conto
	return @dati if ($quanti < 2);	# se sono 1 o 0 i dati sono già ordinati
	my $centro = int $quanti/2;	# altrimento calcolo il punto medio
	# ordino la prima metà dei dati
	my @meta1 = &mergeSort(@dati[0 .. $centro-1]);
	# ordino la seconda metà dei dati
	my @meta2 = &mergeSort(@dati[$centro .. $quanti-1]);
	# e fondo le due metà (ORDINATE) col passo merge
	return &merge(\@meta1,\@meta2);
}

#--------------------------------------------------------------------------
#
# Programma principale
#
sub main {
	my @dati = &leggiDati();		# leggo i dati
	@dati = &mergeSort(@dati);
	&stampaDati(@dati);			# alla fine stampo i risultati
}

#----------------------------------------------------------------------------
#
# stampo i dati
#
sub stampaDati (@) {
	my @dati = @_;
	my $numeroDati = $#dati + 1 ;
	print "Ho letto $numeroDati dati:\n";
	print join( "\n", @dati), "\n";
}

#----------------------------------------------------------------------------
#
# leggo i dati da STDIN e li filtro tenendo i soli validi
#
sub leggiDati () {
	print "inserisci i numeri (positivi)\n";
	my @dati = <STDIN>;		# contiene la lista di dati letti da STDIN
	chop @dati;			# tolgo gli spazi e \n che seguono
	# filtro i dati letti tenendo:
	@dati = grep	{defined 	# butto i valori indefiniti
			&&
			/^[+]?[0-9]+$/	# tengo solo i numeri (interi e positivi)
			}
			@dati;
	return @dati;
}

#---------------------------------- fine ----------------------------------