Problem of the Day
A new programming or logic puzzle every Mon-Fri

N Array Sort

Given n sorted arrays, devise an efficient solution to merge them in to one list. An example would be:

[1,8,19,42]
[4,5,6,20]
[10,21,40,44]

Result: [1,4,5,6,8,10,19,20,21,40,42,44]

Permalink: http://problemotd.com/problem/n-array-sort/

Comments:

  • Anonymous - 9 years, 8 months ago

    #python 2.7
array1 = [1,8,19,42]
array2 = [4,5,6,20]
array3 = [10,21,40,44]

array4 = sorted(array1 + array2 + array3)

print array4

    reply permalink

  • Anonymous - 9 years, 8 months ago

    C#

    using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        List<int[]> arrays = new List<int[]>
        {
            new int[]{1,8,19,42},
            new int[]{4,5,6,20},
            new int[]{10,21,40,44}
        };

        int[] result = MergeArrays(arrays);

        foreach(int i in result)
            Console.WriteLine(i.ToString());
        Console.Read();
    }

    public static int[] MergeArrays(IEnumerable<int[]> arraysToMerge)
    {
        int[] result = new int[arraysToMerge.Sum(x => x.Length)];

        List<Tuple<int[], int>> arraysAndCurrentIndexes = arraysToMerge.Select(x => new Tuple<int[], int>(x, 0)).ToList();

        Tuple<int[], int> lowest = null;

        for (int i = 0; i < result.Length; i++)
        {
            foreach(var tuple in arraysAndCurrentIndexes)
            {
                if (lowest == null)
                {
                    lowest = tuple;
                    continue;
                }

                if (tuple.Item1[tuple.Item2] <= lowest.Item1[lowest.Item2])
                    lowest = tuple;
             }

            result[i] = lowest.Item1[lowest.Item2];
            arraysAndCurrentIndexes.Remove(lowest);
            if (lowest.Item2 + 1 < lowest.Item1.Length)
                arraysAndCurrentIndexes.Add(new Tuple<int[], int>(lowest.Item1, lowest.Item2 + 1));

            lowest = null;
        }

        return result;
    }
}

    reply permalink

  • Anonymous - 9 years, 8 months ago

    Generic Version of the method

    public static T[] MergeArrays<T>(IEnumerable<T[]> arraysToMerge) where T : IComparable
{
    T[] result = new T[arraysToMerge.Sum(x => x.Length)];

    List<Tuple<T[], int>> arraysAndCurrentIndexes = arraysToMerge.Select(x => new Tuple<T[], int>(x, 0)).ToList();

    Tuple<T[], int> lowest = null;

    for (int i = 0; i < result.Length; i++)
    {
        foreach (var tuple in arraysAndCurrentIndexes)
        {
            if (lowest == null)
            {
                lowest = tuple;
                continue;
            }

            if (tuple.Item1[tuple.Item2].CompareTo(lowest.Item1[lowest.Item2]) <= 0)
                lowest = tuple;
        }

        result[i] = lowest.Item1[lowest.Item2];
        arraysAndCurrentIndexes.Remove(lowest);
        if (lowest.Item2 + 1 < lowest.Item1.Length)
            arraysAndCurrentIndexes.Add(new Tuple<T[], int>(lowest.Item1, lowest.Item2 + 1));

        lowest = null;
    }
    return result;
}

    reply permalink

Content curated by @MaxBurstein