This algorithm, which I have included its flowchart as well, takes an array of A[n]
, which is unsorted and unmutatable and an array of B[k]
, which is sorted and includes n
zeroes and then merges, and sorts them together. The entire code in Python and C# can be found here and on this very post.
In C#:
class Program
{
static void Main(string[] args)
{
var inputA = Console.ReadLine();
var inputB = Console.ReadLine();
char[] delimiter = { ' ', ',', '-' };
string[] inputASplit = inputA.Split(delimiter, StringSplitOptions.RemoveEmptyEntries);
string[] inputBSplit = inputB.Split(delimiter, StringSplitOptions.RemoveEmptyEntries);
int[] listA = new int[inputASplit.Length];
int[] listB = new int[inputBSplit.Length];
for (int i = 0; i < inputASplit.Length; i++)
{
listA[i] = int.Parse(inputASplit[i]);
}
for (int i = 0; i < inputBSplit.Length; i++)
{
listB[i] = int.Parse(inputBSplit[i]);
}
int[] concatinatedList = MergeSort(listA, listB);
foreach (var number in concatinatedList)
{
Console.WriteLine(number);
}
Console.ReadKey();
}
static int[] ParseListA(int[] ListA)
{
List<int> newListA = ListA.ToList();
newListA.Sort();
return newListA.ToArray();
}
static int CountZeros(int[] ListB)
{
int zeroCount = 0;
for (int i = 0; i < ListB.Length; i++)
{
if (ListB[i] == 0)
{
zeroCount += 1;
}
}
if (zeroCount == 0)
{
throw new Exception("List B doesn't contain any Zeroes.");
}
return zeroCount;
}
static int[] MergeSort(int[] listA, int[] listB)
{
int[] newListA = ParseListA(listA);
int zeroCount = CountZeros(listB);
int[] newListB = new int[listB.Length - zeroCount];
if (newListA.Length != zeroCount)
{
throw new Exception("There weren't enough buffers!");
}
for (int i = 0; i < listB.Length; i++)
{
if (listB[i] != 0)
{
for (int j = 0; j < newListB.Length; j++)
{
newListB[j] = listB[i];
}
}
}
int[] concatenatedList = newListA.Concat(newListB).ToArray();
Array.Sort(concatenatedList);
return concatenatedList;
}
In Python:
def ParseListA(listA):
newListA = sorted(listA);
return newListA;
def MergeSort(listA, listB):
newListA = ParseListA(listA);
zeroCount = 0;
for number in listB:
if number == 0:
zeroCount += 1;
if zeroCount == 0:
raise ValueError("Needs zeros!");
return;
newlistB = [i for i in listB if i != 0];
return sorted(newListA+newlistB);
def Main():
listAInput = input("Enter List A: ").split(' ');
listBInput = input("Enter List B: ").split(' ');
listA = [int(i) for i in listAInput];
listB = [int(i) for i in listBInput];
print(MergeSort(listA, listB));
Main()