Generate predictable-suffled random array

SO,

The problem

It's well known about pseudo-random numbers. 'Pseudo' actually means, that, despite they are random (i.e. unpredictable) in general, they still will be same in sequence, in which same generator init value was used. For example, in PHP there's mt_srand() function to do that. Example:

mt_srand(1);
var_dump(mt_rand(), mt_rand(), mt_rand());

-no matter, how many time we'll launch our script: generated three numbers will always be same in sequence.

Now, my issue is how to do the same - but for shuffling array. I.e. I want to create a function, which will accept input array to shuffle and seed. Within same seed value shuffling must have consecutive same order. I.e. let we call that function shuffleWithSeed() - and then following should work for every script launch:

$input = ['foo', 'bar', 'baz'];
$test  = shuffleWithSeed($input, 1000);//1000 is just some constant value
var_dump($test); //let it be ['bar', 'foo', 'baz']
$test  = shuffleWithSeed($test, 1000); 
var_dump($test); //let it be ['baz', 'foo', 'bar']
$test  = shuffleWithSeed($test, 1000); 
var_dump($test); //let it be ['baz', 'bar', 'foo']
//...

-i.e. no matter how many times we'll do shuffle for our array - I want for the next script launch ordering sequence will be always the same within one seed value.

My approach

I have in mind this algorithm:

Initialize random numbers generator with passed seed
Generate N random numbers, where N is the number of $input members
Sort numbers from step 2
Make corresponding numbers be dependent from $input keys.

I've implemented this in:

function shuffleWithSeed(array $input, $seed=null)
{
   if(!isset($seed))
   {
      shuffle($input);
      return $input;
   }
   if(!is_int($seed))
   {
      throw new InvalidArgumentException('Invalid seed value');
   }
   mt_srand($seed);
   $random = [];
   foreach($input as $key=>$value)
   {
      $random[$key] = mt_rand();
   }
   asort($random);
   $random = array_combine(array_keys($random), array_values($input));
   ksort($random);
   return $random;
}

-now, also found Fisher-Yates algorithm - but not sure if it can work with pseudorandom numbers (i.e. with seed)

The question

As you can see, I'm doing two sorts in my function - first by values and second by keys.

Can this be done with one sort? Or without sort at all? Input array could be large, so I want to avoid this.
However, may be my algorithm is not well? If yes, what other options could be suggested?

Here's a copy and paste of a function I have implemented a while ago for exactly this purpose:

/**
 * Shuffles an array in a repeatable manner, if the same $seed is provided.
 * 
 * @param array &$items The array to be shuffled.
 * @param integer $seed The result of the shuffle will be the same for the same input ($items and $seed). If not given, uses the current time as seed.
 * @return void
 */
protected function seeded_shuffle(array &$items, $seed = false) {
    $items = array_values($items);
    mt_srand($seed ? $seed : time());
    for ($i = count($items) - 1; $i > 0; $i--) {
        $j = mt_rand(0, $i);
        list($items[$i], $items[$j]) = array($items[$j], $items[$i]);
    }
}

It implements a simple Fisher-Yates shuffle with a seeded random number generator.