What would be the best data structure for a Merge Search?

Question

I want to do a merge sort in c#. I know the premise of the sort but I can't think how to store the values when the data is split in halves. Obviously the data will be split and again and again until the individual values are found and then they are stored. After that comes the comparison. I haven't started coding yet so I am open to suggestions. For my previous bubble and binary insertion sorts I used arrays. The data sets will be variable in size so I want something to accommodate this.

    MergeString MergeSort = new MergeString();
                int StringCount = MergeSort.GetNumberOfStrings();
                string[] UnsortedStringList = MergeSort.GetListOfStrings(StringCount);


public class MergeInt
{
public int GetNumberOfNumbers()
{
    bool isParsable = false;
    int NumberCount = 0;

    do
    {
        Console.WriteLine("How many numbers are in the unsorted list?");

        string NumberOfNumbers = Console.ReadLine();

        isParsable = int.TryParse(NumberOfNumbers, out NumberCount);
    } while (isParsable == false);
    return NumberCount;
}
public int[] GetListOfNumbers(int NumberCount)
{
    bool isParsable = false;
    int[] UnsortedNumberList = new int[NumberCount];

    for (int i = 0; i < NumberCount; i++)
    {
        int Number = 0;

        do
        {
            Console.WriteLine("What number is in the list?");

            string NumberString = Console.ReadLine();

            isParsable = int.TryParse(NumberString, out Number);
        } while (isParsable == false);

        UnsortedNumberList[i] = Number;
    }

    return UnsortedNumberList;
}
public void SortList(int[] a)
{
   

    int split = a.Length / 2;

    Console.WriteLine(split);


}

}

Answer 1

Merge sort requires an extra buffer to store temporary data. To keep it simple you should probably just use arrays for everything. I'm not sure I would call this a "data structure", since it is just a plain memory buffer.

For the actual merge code I would probably recommend using Span<T>, this lets you refer to a section of memory inside a buffer by Sliceing the data. An array should be convertible to a span, but you can also call AsSpan.

For this kind of problem I would probably go for recursive solution, and I would expect the major difficulty will be to avoid of by one errors, and ensuring you are swapping and merging buffers correctly.