Create sorted array from multiple pre-sorted arrays

Question

I would like to create a sorted array from a variable number of pre-sorted arrays.

Given {A1, ..., An} which are pre-sorted arrays, I would like to create At, which is the combination of {A1, ..., An} and is sorted in the same way.

Example :

Given :
A1 = [2, 4, 9, 16]
A2 = [-3, 4, 98, 116]
...
An = [1, 7, 17, 76, 512]

I would like :
At = [-3, 1, 2, 4, 4, 9, 16, 17, 76, 98, 116, 512]

What it is the most efficient way to compute this array ?

Thanks

I won't put this as an 'answer', since it doesn't directly answer your question, but depending on your implementation requirements you may want to look at using an SplHeap. This is an efficient Heap datastructure (a tree, really) that lets you define a compare() method, to ensure your heap is always properly ordered. The downside is it only preserves a pointer to the top of the heap (ie the least element as shown by the compares), so if you need to iterate it many times, you'll need to load it into another datastructure. http://php.net/manual/en/class.splheap.php — Josh from Qaribou, Mar 12 '15 at 13:13
Seems pretty simple, maybe not the most efficient, but merge and sort again. Unless this is purely academic that's what I would do. — AbraCadaver, Mar 12 '15 at 14:02
@JoshfromQaribou it's not better than sort(array_merge(arrays)) - same complexity. — iced, Mar 12 '15 at 15:53

score 1 · Answer 1 · answered Mar 12 '15 at 13:04

1

It's simple. We have A1..AN - pre-sorted lists and same amount of indexes I1..IN set to zero (for zero-based lists). Now we need to form merged list from this. To do this we need to find smallest (or biggest depends on what's initial sort order) element from all these lists. It's obvious that this is one of the A1[I1] A2[I2] .. AN[IN] element. So we just go through all these elements and choose smallest. Let's say it was element in A2. We put it into our new big list and increment I2. Now we have same situation as in the beginning and should repeat all these steps again or stop if all lists exhausted.

Example:

A1 = [1, 2, 6]
A2 = [2, 4, 5]

A = []
I1 = 0
I2 = 0
-------------
A = [1]
I1 = 1
I2 = 0
-------------
A = [1, 2]
I1 = 2
I2 = 0
-------------
A = [1, 2, 2]
I1 = 2
I2 = 1
...

answered Mar 12 '15 at 13:04

iced

1,562
8
10

Looks good to me ! Any chance you have a PHP implementation for this algorithm ? I am working on it anyway. – Félix Veysseyre Mar 12 '15 at 14:39
last time I wrote some php was in previous century, so no, thank you. but come on - it's really trivial. – iced Mar 12 '15 at 15:51
1

ok - I googled some code for you. http://www.phpbuilder.com/snippet/detail.php?type=snippet&id=1068 you need function merge which merges just two sorted arrays (same algo as I described). you can reduce your array list into one array using this merge. `$a = []; foreach ($arrays as $sa) { $a = merge($a, $sa) }` (pseudocode, not even sure how to create empty array in php ;]). It's still not optimal, but way way way better than your implementation. – iced Mar 12 '15 at 15:56

score 0 · Accepted Answer · edited Sep 12 '22 at 10:41

I have implemented a function doing what I want.

What do you think of the performance ? Do you have any advice to improve it ?

Sorting function:

function sortPreSortedArrays($arrays, $comparisonFunction, $order = 'asc')
{
    $sortedArray = array();

    /* Sort */

    while(sizeof($arrays) !== 0)
    {
        /* Find the greatest value */

        $max = true;
        $keyMax = -1;

        foreach($arrays as $key => $array)
        {
            if($max === true || $comparisonFunction(end($array), $max))
            {
                $max = end($array);
                $keyMax = $key;
            }
        }

        /* Take the greatest value */

        array_push($sortedArray, array_pop($arrays[$keyMax]));
        if(sizeof($arrays[$keyMax]) === 0) unset($arrays[$keyMax]);
    }

    /* Return */

    if($order === 'asc')
        return array_reverse($sortedArray);
    else
        return $sortedArray;

Comparison function:

function compareLogArrayDate($log1, $log2)
{
    $t1 = $log1['date'];
    $t2 = $log2['date'];

    return ($t1 > $t2) ? true : false;
}

Edit: In order to improved the performancse, I have tried do use the most efficient array functions (array_pop O(1) instead of array_shift O(n). Nevertheless I am still using unset. :|

score -1 · Answer 3 · answered Mar 12 '15 at 16:35

$A1 = [2, 4, 9, 16];
$A2 = [-3, 4, 98, 116];
$An = [1, 7, 17, 76, 512];


// create arrays of ith elements
$return = call_user_func_array('array_map', [null, $A1, $A2, $An]);
// sort arrays
array_walk($return, 'sort');
// create new arrays
$return = call_user_func_array('array_merge', $return);
// remove null values lefted after first operation
$return = array_filter($return, 'is_scalar');
var_dump($return);

Create sorted array from multiple pre-sorted arrays

3 Answers3

Linked