Programming Challenge: Merge an arbitrary number of arrays in sorted order.

Here is my sed solution:

:a
s/[^0-9,]//g
s/(,|$)+/%,/g
:b
s/$/@0@1@2@3@4@5@6@7@8@9@/
:c
s/^([0-9]*)([0-9])%([0-9]*,)(.*@\2[^@]*)@/\4\1%\2\3@/
tc
s/@(.|$)//g
/(^|,)[^%]/{s/(,|^)%/\10%/g;
bb}
s/%0*([^,])|,$/\1/g
s/^,//
N
s/\n/,/
ba

Inputs are comma separated lists of numbers, each newline the currently sorted list is outputted, so if you want the whole list, pipe it into tail -n1.

Internally it uses radix sort (@0@1@2@3@4@5@6@7@8@9@ are the marks for the buckets and it adds padding zeros in front of the numbers as needed and removes them at the end).

Edit: Edited it so now it only outputs the list at EOF.

This is the least efficient I can make it (Python 3), without adding irrelevant code in between:

def sort_arrays(*a):
  return list(sorted(__import__('functools').reduce(__import__('operator').concat, a)))

Just call it like this: sort_arrays([5,7,1], [2,8,3], [9,5,7])

Hmm fun.

Naive (straight forward):

def sort_arrays(*arrays):
	compiled = list()
	for array in arrays:
		compiled += array 
	print(compiled.sort())

It's got a time complexity of O(nlogm) where n is the total number of elements in all arrays. I'll try to come up with some more fun ones when I get home (maybe a generator? multithreaded?)

Super simple Python. Read a line, create a new list of those values as _int_s, throw it on to a master list, then unpack everything and sort it.

import sys


arrays = []
for line in sys.stdin:
    line = line.strip()
    if not line:
        break
    arrays.append([int(e) for e in line.split(' ') if e])
print(sorted(i for j in arrays for i in j))

The easiest thing to do is cast to ints when reading off stdin, but sorted supports a key parameter to specify how to sort the data as well.

Similar thing in Go, but only keeping a single slice of ints and appending to it each time. Not likely a performant usage of append.

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var ints []int
	reader := bufio.NewReader(os.Stdin)
	for {
		text, err := reader.ReadString('\n')
		if err != nil {
			panic(err)
		}
		text = strings.TrimSpace(text)
		if text == "" {
			break
		}
		for _, part := range strings.Split(text, " ") {
			partVal, err := strconv.Atoi(strings.TrimSpace(part))
			if err != nil {
				panic(err)
			}
			ints = append(ints, partVal)
		}
	}
	sort.Ints(ints)
	fmt.Println(ints)
}

Python2

def sort_list_of_lists( lol ):
    combined = sum( lol, [] )
    combined.sort()
    return combined

That's just the function, I leave the I/O to the front-end people.

Just because of all the PHP umbrage around here lately, I wrote my solution in it. 😝

function combineAndSortArrays(...$params){
        $arr = array_reduce($params, 'array_merge', []);
        sort($arr);
        return $arr;
}

combineAndSortArrays() is a variadic function that accepts as many arrays as you can throw at it. It combines them into a single array and then sorts it by value.

I'll use my own sorting algorithm (but I'm sure it already exists):

Theory

Let's have a method that gets unlimited amount of arrays (params int[][] in c#). We build some collection, probably binary tree. For each element in each of the arrays, I'll append the number into tree (or custom collection that works very similar to binary tree). Because the arrays are not ordered, we can safely choose first element of first array as tree root, as it's equivalent to choosing random element. I don't know if it's worth balancing the tree in the process.

After we have all elements, we return the tree (or convert it to array and return it).

Time complexity should be, where N is number of total elements, N*log(N), plus, if we convert the tree to an array afterwards, N.

It would be interesting to compare it to the most simple way how to do it, simply add everything to single array and then call .Sort().

Code

        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[][] input = new int[10][];
            for(int i = 0; i < input.Length; i++)
            {
                input[i] = new int[10];
                for(int j = 0; j < input[i].Length; j++)
                {
                    input[i][j] = rnd.Next(101);
                }
            }
            Stopwatch sw = new Stopwatch();
            const int tries = 100;
            List<long> t1 = new List<long>(tries);
            List<long> t2 = new List<long>(tries);
            for (int i = 0; i < tries; i++)
            {
                sw.Start();
                SortArraysSimpleMethod(input).ToArray(); // Convert result to array, otherwise the code will never be executed, as LINQ uses lazy loading
                sw.Stop();
                t1.Add(sw.ElapsedMilliseconds);
                sw.Reset();

                sw.Start();
                SortArraysComplexMethod(input);
                sw.Stop();
                t2.Add(sw.ElapsedMilliseconds);
                sw.Reset();

                Console.Write(".");
            }
            Console.Write("\n");

            Console.WriteLine(t1.Average());
            Console.WriteLine(t2.Average());
            Console.ReadKey();
            return;
        }


        private static IEnumerable<int> SortArraysSimpleMethod(params int[][] arrays)
        {
            int[] result = new int[arrays.Select(array => array.Length).Sum()];
            int i = 0;
            foreach(int[] array in arrays)
            {
                foreach(int element in array)
                {
                    result[i] = element;
                    i++;
                }
            }
            return result.OrderBy(element => element);
        }

        private static IEnumerable<int> SortArraysComplexMethod(params int[][] arrays)
        {
            Node tree = null;
            foreach(int[] array in arrays)
            {
                foreach(int element in array)
                {
                    if(tree == null)
                    {
                        tree = new Node() { value = element };
                    }
                    else
                    {
                        tree.AddChild(element);
                    }
                }
            }

            // Read child
            List<int> values = new List<int>(arrays.Select(array => array.Length).Sum());
            tree.ReadValues(values);
            return values;
        }


        class Node
        {
            public Node leftChild;
            public Node rightChild;
            public Node parent;
            public int value;

            public void AddChild(int value)
            {
                if(value >= this.value)
                {
                    if(rightChild == null)
                    {
                        rightChild = new Node() { parent = this, value = value };
                    }
                    else
                    {
                        rightChild.AddChild(value);
                    }
                }
                else
                {
                    if(leftChild == null)
                    {
                        leftChild = new Node() { parent = this, value = value };
                    }
                    else
                    {
                        leftChild.AddChild(value);
                    }
                }
            }

            public void ReadValues(List<int> collection)
            {
                if(leftChild != null)
                {
                    leftChild.ReadValues(collection);
                }
                collection.Add(value);
                if(rightChild != null)
                {
                    rightChild.ReadValues(collection);
                }
            }
        }

Results

For small inputs, like 10*10, the results were surprising - the simple method had average (from 100 tries) 0.07ms, the complex one 0.01ms. For input 100*50, the simple one had average 1.62ms, and the complex one 2.13 ms. For input 100*1000, (this time average of 10 tries), the simple one had average 53.9ms and the complex one 1274.2ms.

^{Edit: Added syntax highlighting}

Now for Python:

fn = lambda x: sorted(sum(x, []))

Don't have time to test this quite yet but it should work:

#include <algorithm>
#include <iterator>
#include <vector>

template <typename T>
std::vector<T> flatten_and_sort(std::vector<std::vector<T>> arrays) {
	std::vector<T> result;
	auto it = std::back_inserter(result);
	
	for (auto &array : arrays) {
		std::move(array.begin(), array.end(), it);
	}
	
	std::sort(result.begin(), result.end());
	
	return result;
}

Passing the argument by value allows the caller to choose whether to pass an lvalue to be copied or an rvalue to be consumed.

Flattening is O(n) where n is the total number of elements in all the arrays, and sorting is O(n log n).

Not sure if using Python's itertools.chain is cheating…

Python 3.7.0 (default, Jul 15 2018, 14:01:53) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.5.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from operator import itemgetter

In [2]: from itertools import chain

In [3]: def multi_sort_gen(*iterables, **kwargs):
   ...:     yield from sorted(chain(*iterables), **kwargs)
   ...:     
   
In [4]: list(multi_sort_gen([(1,3), (1,2), (1,1)], [(2,10), (2,9), (2,8)], key=itemgetter(1)))
Out[4]: [(1, 1), (1, 2), (1, 3), (2, 8), (2, 9), (2, 10)]

In [5]: list(multi_sort_gen([(1,3), (1,2), (1,1)], [(2,10), (2,9), (2,8)], key=itemgetter(1), reverse=True))
Out[5]: [(2, 10), (2, 9), (2, 8), (1, 3), (1, 2), (1, 1)]

In [6]: from random import randint

In [7]: arrays = [[randint(0,9) for _ in range(10 ** 3)] for _ in range(10 ** 3)]

In [8]: %timeit result = list(multi_sort_gen(*arrays))
263 ms ± 11.8 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: arrays = [[(i, randint(0,9)) for _ in range(10 ** 3)] for i in range(10 ** 3)]

In [10]: %timeit result = list(multi_sort_gen(*arrays, key=itemgetter(1)))
570 ms ± 46.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

I learned that heapq.merge exists and it claims:

Help on function merge in module heapq:

merge(*iterables, key=None, reverse=False)
    Merge multiple sorted inputs into a single sorted output.
    
    Similar to sorted(itertools.chain(*iterables)) but returns a generator,
    does not pull the data into memory all at once, and assumes that each of
    the input streams is already sorted (smallest to largest).
    
    >>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
    [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]
    
    If *key* is not None, applies a key function to each element to determine
    its sort order.
    
    >>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len))
    ['dog', 'cat', 'fish', 'horse', 'kangaroo']

This has the disadvantage that the inputs must be pre-sorted. The advantage, though, is that it does not require all inputs to fit in memory (whereas my solution above does). Nice to know that the tradeoff of space for time can be made here.

In [12]: import heapq

In [14]: %timeit result = list(heapq.merge(*(sorted(a, key=itemgetter(1)) for a in arrays), key=itemgetter(1)))      
3.24 s ± 252 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

The magic that is JavaScript ES6... when working through this, I had a similar real world problem this week, so still rather fresh. Get a messy array => into new array of arrays with groups of 3 obj. Fun times.

• Don't hate on the web dev... we program too. Sometimes.*

let overallArr = [];
const arr = [[1,2,3], [3,4,5,], [5,6,7,8]]

function sortArr (current, arr) {
  let currentArr = current;
  let tempArr = [];
  
  for (let i=0; i < arr.length; i++) {
    let innerArr = arr[i];
    tempArr = [...tempArr, ...innerArr]
  }

// Not the most efficient in large sets
// https://gist.github.com/telekosmos/3b62a31a5c43f40849bb#gistcomment-1739870
  return overallArr = new Set(tempArr.sort())
}

sortArr(overallArr, arr)
console.log(sortArr(overallArr, arr))