For question 1: In general, WRT grep (which can only remove elements): yes, the relative order is maintained. For Far More Than You Ever Wanted to Know about this, see the recent Order in which grep/map receive elements.

For question 2: In general, WRT map (which is allowed to insert elements) the answer is no:

>perl -wMstrict -le
"my @sorted = (1, 2, 3, 4, 5, 6);
 my @unsorted = map { $_, 99 } @sorted;
 print qq{@unsorted};
"
1 99 2 99 3 99 4 99 5 99 6 99
[download]