No Schwartzian transorm, but this seems to do it:

#!/usr/bin/perl -w

use strict;

# Build a utility array for sorting by size
our @sizes=qw(s m l xl);
our %sizeval;
{
  my $i = 0;
  $sizeval{$_}=$i++
      foreach @sizes;
}
    
# Build the array to test
my @arr;
while (<DATA>)
{
  chomp;
  push(@arr,{ sortval => $_ });
}

# Now sort the results and print them
foreach (sort bysizecolor @arr)
{
  print $_->{sortval},"\n";
}

# Sort hashrefs by size and color 
sub bysizecolor
{
  my ($a_size,$a_color) = getsizecolor($a->{sortval})
      or warn("Couldn't parse '$a'"),return 0;
  my ($b_size,$b_color) = getsizecolor($b->{sortval})
      or warn("Couldn't parse '$b'"), return 0;
  return bysize($a_size, $b_size) || bycolor($a_color, $b_color);
}

# Compare two sizes
sub bysize
{
  my($a,$b)=@_;
  $sizeval{lc $a} <=> $sizeval{lc $b};
}

# Compare two colors
sub bycolor
{
  my($a,$b)=@_;
  lc $a cmp lc $b;
}

# Extract the size and color from a string
sub getsizecolor
{
  return ($_[0] =~ m!\w+:\s(\w+),\s\w+:\s(\w+)!);
}


__DATA__
size: L, color: White
size: M, color: Orange
size: M, color: White
size: M, color: White
size: S, color: Orange
size: S, color: White
size: Xl, color: Orange
size: Xl, color: White
size: Xl, color: White
[download]