Skip to content

Instantly share code, notes, and snippets.

@adamlum
Created December 28, 2012 21:03
Show Gist options
  • Save adamlum/4401868 to your computer and use it in GitHub Desktop.
Save adamlum/4401868 to your computer and use it in GitHub Desktop.
Write a function that merges an array of already sorted arrays, producing one large, still sorted array. (included a C# integer array merge sort method)
/****************************************************************
Adam Lum
12/28/2012
Coding for Interviews on Merge Sort
http://codingforinterviews.com
Write a function that merges an array of already sorted arrays,
producing one large, still sorted array.
(included a C# integer array merge sort method)
*******************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CodingInterviewPractice_2012_12_24
{
class Program
{
static void Main(string[] args)
{
int[] firstSorted = { 0, 5, 8, 9 };
int[] secondSorted = { 1, 2, 7 };
int[] thirdSorted = { 10 };
int[][] arrayOfSorted = { firstSorted, secondSorted, thirdSorted};
int[] largeSorted = mergeArrayOfSortedArrays(arrayOfSorted);
for(int i = 0; i < largeSorted.Length; i++)
{
if (i > 0)
{
Console.Write(", ");
}
Console.Write(largeSorted[i]);
}
}
static int[] mergeArrayOfSortedArrays(int[][] _arrayOfSorted)
{
int[] returnArray = new int[0];
for (int i = 0; i < _arrayOfSorted.Length; i++)
{
returnArray = merge(returnArray, _arrayOfSorted[i]);
}
return returnArray;
}
static int[] mergeSort(int[] _unsorted)
{
if (_unsorted.Length > 1)
{
int[] first, second;
if (_unsorted.Length % 2 == 0)
{
first = new int[_unsorted.Length / 2];
second = new int[_unsorted.Length / 2];
}
else
{
first = new int[_unsorted.Length / 2];
second = new int[(_unsorted.Length / 2) + 1];
}
Array.Copy(_unsorted, first, first.Length);
Array.Copy(_unsorted, first.Length, second, 0, second.Length);
return merge(mergeSort(first), mergeSort(second));
}
else
{
return _unsorted;
}
}
static int[] merge(int[] _first, int[] _second)
{
int[] sorted = new int[_first.Length + _second.Length];
int firstIndex = 0, secondIndex = 0;
for (int i = 0; i < sorted.Length; i++)
{
if (firstIndex == _first.Length)
{
sorted[i] = _second[secondIndex];
secondIndex++;
}
else if (secondIndex == _second.Length)
{
sorted[i] = _first[firstIndex];
firstIndex++;
}
else if (_first[firstIndex] < _second[secondIndex])
{
sorted[i] = _first[firstIndex];
firstIndex++;
}
else
{
sorted[i] = _second[secondIndex];
secondIndex++;
}
}
return sorted;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment