Merge Sorting a String Array in C#

Question

I am attempting to program an array sorting and searching program that will be handling 600 items within a string array.The data which is to be sorted looks as such:

2017 | 25 | January | 9994750 | 27.640 | 36.800 | DODECANESE ISLANDS, GREECE | 1485307173 | 01:19:33 | 4.000 |

I have been attempting to implement a merge sort to sort this data. However, I am unable to figure out how to convert a merge sort program designed for an int array into one designed for sorting a string array. Could anyone explain how I could do this?

Though this can be done via the use of existing built in functions I have been attempting this in preparation for university courseworks next years and so I am having to program the Merge sort from scratch and not use the built in functions.

Side note: I must note that I am aware that in its current form the program could not sort months naturally even with the merge sort but that is something I already have a work round for once I can get the merge sort operating as intended.

The current merge sort program:

        static public void MainMerge(string[] numbers, int left, int mid, int right)
    {
        int[] temp = new int[25];
        int i, eol, num, pos;

        eol = (mid - 1);
        pos = left;
        num = (right - left + 1);

        while ((left <= eol) && (mid <= right))
        {
            if (numbers[left].CompareTo(numbers[mid]))
                temp[pos++] = numbers[left++];
            else
                temp[pos++] = numbers[mid++];
        }

        while (left <= eol)
            temp[pos++] = numbers[left++];

        while (mid <= right)
            temp[pos++] = numbers[mid++];

        for (i = 0; i < num; i++)
        {
            numbers[right] = temp[right];
            right--;
        }
    }

    static public void SortMerge(string[] numbers, int left, int right)
    {
        int mid;

        if (right > left)
        {
            mid = (right + left) / 2;
            SortMerge(numbers, left, mid);
            SortMerge(numbers, (mid + 1), right);

            MainMerge(numbers, left, (mid + 1), right);
        }
    }

Trying to repurpose code is often more work than it's worth. It seems like a simple enough task that you would be better off starting from scratch. — coinbird
– coinbird, Commented Apr 25, 2017 at 19:41
@coinbird what? This is very straightforward using generics. There is no reason to "start from scratch" — user47589
– user47589, Commented Apr 25, 2017 at 19:41
You should implement the sort using generics that implement IComparable. public void MergeSort<T>(this T[] elements) where T : IComparable { } — Blake Thingstad
– Blake Thingstad, Commented Apr 25, 2017 at 19:42
Is there a reason you can't use Array.Sort(array); instead of implementing your own sorting? — Blake Thingstad
– Blake Thingstad, Commented Apr 25, 2017 at 20:08
@GiggyLapisar getting better at coding would imply you're learning to do things the right way. Using generics would be the right way, here. Duplicating your code and replacing string with int will work, but its a terrible solution. — user47589
– user47589, Commented Apr 25, 2017 at 20:27

score 3 · Accepted Answer · 2017-04-25 21:07:32Z

3

To allow your algorithm to operate on different types, we use C# Generics. I made the following changes to your code:

Renamed the numbers parameter to values, to better fit the other changes
Changed the data type of the array from string to T
Added a type constraint, so T is required to be comparable to other T
Changed the type of the temp array to T as well.
You're already using CompareTo to do your comparison, so no other code changes are needed edit: actually, IComparable.CompareTo has a different return value than string.CompareTo, so a small adjustment will need to be made.

I used IComparable<T> instead of IComparable. Both should work equally well for your purposes.

Code follows:

static public void MainMerge<T>(T[] values, int left, int mid, int right) where T : IComparable<T>
{
    T[] temp = new T[25];
    int i, eol, num, pos;

    eol = (mid - 1);
    pos = left;
    num = (right - left + 1);

    while ((left <= eol) && (mid <= right))
    {
        if (values[left].CompareTo(values[mid]))
            temp[pos++] = values[left++];
        else
            temp[pos++] = values[mid++];
    }

    while (left <= eol)
        temp[pos++] = values[left++];

    while (mid <= right)
        temp[pos++] = values[mid++];

    for (i = 0; i < num; i++)
    {
        values[right] = temp[right];
        right--;
    }
}

static public void SortMerge<T>(T[] values, int left, int right) where T : IComparable<T>
{
    int mid;

    if (right > left)
    {
        mid = (right + left) / 2;
        SortMerge(values, left, mid);
        SortMerge(values, (mid + 1), right);

        MainMerge(values, left, (mid + 1), right);
    }
}

You can then call this on an array of any type that is comparable to itself. int and string should both work just fine.

edited Apr 25, 2017 at 21:07

answered Apr 25, 2017 at 20:39

user47589

Sign up to request clarification or add additional context in comments.

4 Comments

GiggyLapisar Over a year ago

Seems like it should work. For some reason though the .CompareTo part throws a "Cannot implicity convert int to bool" error.

user47589 Over a year ago

@GiggyLapisar okay, CompareTo returns 0 if the items are equal, -1 if the left item sorts first, or 1 if the right item sorts first. So compare to the appropriate integer. I think you should add < 0 to the condition. Sorry, I don't have an editor available atm. Should be: if (values[left].CompareTo(values[mid]) < 0). I think

user47589 Over a year ago

@GiggyLapisar See remarks

GiggyLapisar Over a year ago

Yeah that works perfectly. Thank you so much. Now I'll just have to quickly read through it to truely understand how it works.

Collectives™ on Stack Overflow

Merge Sorting a String Array in C#

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related