A quick test made at the command line, copying and pasting BrowserUk's test data (thanks to him), and separating the data into two parts:

$ perl -e '
> use strict;
> use warnings;
> my $in =
> "a 123
> a 125
> b 127
> a 129
> a 130
> b 131
> a 132
> b 133";
>
> my @a = grep /a/, split /\n/, $in;
> print shift @a, " => $_\n" for grep /b/, split /\n/, $in;
> '
a 123 => b 127
a 125 => b 131
a 129 => b 133
[download]

Just 2 lines of actual code, but not golfing either in the slightest manner, I think it is fairly clear and straight forward.

Separating the data into two lots has an additional advantage if the input data is not ordered because sorting is just trivial:

$ perl -e '
> use strict;
> use warnings;
> my $in =
> "a 123
> a 125
> b 131
> a 130
> b 127
> a 129
> a 132
> b 133";
>
> my @a = sort grep /a/, split /\n/, $in;
> print shift @a, " => $_\n" for sort grep /b/, split /\n/, $in;
> '
a 123 => b 127
a 125 => b 131
a 129 => b 133
[download]

Update: I forgot to include the calculation of the elapsed time, but this is so simple that it is left as an exercise to the OP.