Naive solution
You can use array_filter to create two groups according to gender. Then zip the groups into pairs using array_map and run the pairs through array_reduce to flatten the structure:
$males = array_filter($students, function ($e) {
return $e["gender"] === "male";
});
$females = array_filter($students, function ($e) {
return $e["gender"] === "female";
});
$zipped = array_map(null, $males, $females);
$result = array_reduce($zipped, function ($a, $e) {
if ($e[0]) $a[] = $e[0];
if ($e[1]) $a[] = $e[1];
return $a;
}, []);
Time complexity is O(n).
Reducing overhead
If the first solution has too much overhead, consider eliminating function calls. It's still O(n) with two passes but branch prediction should handle situations with a wide quantity imbalance between the genders in the merge loop:
foreach ($students as $student) {
if ($student["gender"] === "male") {
$males[]= $student;
}
else {
$females[]= $student;
}
}
$male_count = count($males);
$female_count = count($females);
for ($i = 0, $j = 0; $i < $male_count || $j < $female_count;) {
if ($i < count($males)) {
$result[]= $males[$i++];
}
if ($j < count($females)) {
$result[]= $females[$j++];
}
}
Generalization
The above code assumes two things: (1) "male" should always be first even if it produces a suboptimal interleaving (per OP's specification) and (2) only two "gender" values exist.
The first problem can be solved by modifying the above snippets to swap the array order during the zipping stage to prefer the longest array first.
The second problem can be solved using array_reduce to create groupings of array elements per unique value for the target key, then removing hardcoded values in favor of iteration over these groups sorted descending by frequency (tie-breaking logic can be added).
Time complexity for the below code is O(n + k*log(k)) where k is the number of unique values. Worst case, all entries are totally or nearly unique, in which case we have an O(n log(n)) solution due to a superfluous sort, but it's O(n) if k is constant, as in OP's case.
Note that PHP sort routines are not stable, so you'll need to pack and unpack the array into index/element pairs or use a custom tie-breaking policy other than index.
<?php
function interleave_values($arr, $key) {
$unique_values = array_unique(array_column($arr, $key));
$buckets = array_reduce($arr, function ($a, $e) use ($key) {
$a[$e[$key]][] = $e;
return $a;
}, []);
rsort($buckets);
$zipped = array_map(null, ...$buckets);
return array_reduce($zipped, function ($a, $e) {
foreach ($e as $f) {
if (!$f) break;
$a[] = $f;
}
return $a;
}, []);
}
$test = [
["k" => 1],
["k" => 2],
["k" => 1],
["k" => 3],
["k" => 3],
["k" => 1],
["k" => 2],
["k" => 2],
["k" => 2],
];
var_export(interleave_values($test, "k"));
Output:
array (
0 =>
array (
'k' => 2,
),
1 =>
array (
'k' => 1,
),
2 =>
array (
'k' => 3,
),
3 =>
array (
'k' => 2,
),
4 =>
array (
'k' => 1,
),
5 =>
array (
'k' => 3,
),
6 =>
array (
'k' => 2,
),
7 =>
array (
'k' => 1,
),
8 =>
array (
'k' => 2,
),
)
