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