Big-O complexity calculation for a merge and sort function

I have the following code which basically takes a list of sorted integer arrays and merges them together removing the duplicates.

I have tried to do the complexity analysis and came to a rough conclusion that it may be O(n2) order. Could you please see if my understanding is correct here.

Also, if you could suggest ways to make the code better in terms of its running time, I would really be grateful.

If you need the implementation of PrioQueue, please let me know.

```
public ArrayList MergeMultiple(Object[] input)
{
ArrayList result = new ArrayList();
int activeArrayIndex = -1;
int inputArrayCount = input.Count();

// Keep track of indices of the arrays
int[] indices = new int[inputArrayCount];

// Keep track of whether the end has been reached for each array
bool[] endOfArray = new bool[inputArrayCount];

// Heap
PrioQueue heap = new PrioQueue();

while (endOfArray.Contains(false)) // O(N)
{
for (int i = 0; i < inputArrayCount; i++) // O(N)
{
int[] active = (int[])input[i];
int index = indices[i];
if (activeArrayIndex == -1 || (i == activeArrayIndex && !endOfArray[i]))
{
int value = active[index];

// Add value to the heap
heap.Enqueue(i + "|" + value, value); // O(N)??
}
}

// Add to result
if (!heap.IsEmpty())
{
activeArrayIndex = activeArrayIndex == -1 ? 0 : activeArrayIndex;

string activeArrayIndexWithVal = (string)heap.Dequeue(); // O(1)

string[] activeArrayObject = activeArrayIndexWithVal.Split('|');

// Identifying active array
activeArrayIndex = Convert.ToInt32(activeArrayObject[0]);
int[] activeArray = (int[])input[activeArrayIndex];

// Adding value to result object if not already in the array list
if (!result.Contains(activeArrayObject[1])) // O(N

If N == number of input arrays and M == length of the longest input array then your outer while loop will run M times with the check condition being O(N) so your outer loop is O(MN). The inner loop runsNtimes and the heap insert isO(log(N))so your inner body isO(Nlog(N)). Resulting in a total complexity of O(M N^2 log(N))

Some review:

I find the entire code very confusing and hard to read. You keep track of different properties for the same array in disjoint helper arrays (indices and endOfArray) while they should be combined in a single state object.

Also your input is Object[] while obviously you expect a list of int[] so why not express that in your parameter directly like: List input.

Your result is a non-generic ArrayList so it's really hard to know what the exact return type of the elements is. Reading through the code it looks like the elements get returned as strings which is probably very confusing for the user - why on earth would a method to which I pass a list of integer arrays return the merged result as an array of strings?

If I read your intention correctly then you want to merge the input arrays, remove all duplicates and return the result ordered. You can write that very nicely with LINQ:

public List MergeLists(List lists)
{
    return lists.SelectMany(l => l) // flatten into single collection
                .Distinct()         // remove duplicates
                .OrderBy(x => x)    // sort the result
                .ToList();          // build result list
}

Assuming all N arrays have the same maximum length M then the complexity should be:

• Distinct() is in the order of O(N * M)

• OrderBy() is in the order of O(N M log(N * M))

• ToList() is in the order of O(N * M)

Which means the resulting complexity is O(N M log(N * M) so you have cut it down to linear in terms of number of input arrays and the code is significantly shorter, easier to read and maintain and very likely to contains fewer bugs.

StackExchange Code Review Q#44287, answer score: 6