#!pil
=pod
=head1 DESCRIPTION
This is a bottom-up mergesort from the Algorithms
book (see READTHEM file). It was first translated
from Haskell to PIL^N by tewk, and then finished
off by myself.
=head1 AUTHOR
Stevan Little <stevan@iinteractive.com>
=cut
&compare := -> $a, $b {
$a`eq($b)`if_else(
-> { 0 },
-> {
$a`lt($b)`if_else(
-> { -1 },
-> { 1 }
);
}
);
};
&split := -> @lst, @acc {
&redo := &?SUB;
@lst`length()`eq(0)`if_else(
-> { @acc },
-> { &redo`(@lst`splice(1), @acc`push([ @lst`fetch(0) ])) }
);
};
&merge := -> @l1, @l2 {
&redo := &?SUB;
@l1`is_nil()`if_else(
-> { @l2 },
-> {
@l1`is_empty()`if_else(
-> { @l2 },
-> {
@l2`is_nil()`if_else(
-> { @l1 },
-> {
@l2`is_empty()`if_else(
-> { @l1 },
-> {
$hl1 := @l1`fetch(0);
$hl2 := @l2`fetch(0);
&compare`($hl1, $hl2)`lt(0)`if_else(
->{
[ $hl1 ]`concat( &redo`( @l1`splice(1), @l2 ) )
},
->{
[ $hl2 ]`concat( &redo`( @l1, @l2`splice(1) ) )
}
);
}
);
}
);
}
);
}
);
};
&mergepairs := -> @lst {
&redo := &?SUB;
@lst`length()`le(1)`if_else(
-> { @lst`fetch(0) },
-> {
&merge`(
&merge`(@lst`fetch(0), @lst`fetch(1)),
&redo`(@lst`splice(2))
);
}
);
};
&mergesort := -> @lst {
-> @lst {
&redo := &?SUB;
@lst`length()`eq(1)`if_else(
-> { @lst`fetch(0) },
-> { &mergepairs`(@lst) }
)
}`(&split`(@lst, []))
};
#&mergesort`(['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']);
&mergesort`([33, 1212, 9, 1, 3433, 2, 3, 7, 9, 9, 45, 35, 27, 44, 10101, 0, -50]);