in-place Merge Sort | C#

Question

I have written a program for merge sort and The program works fine until at a point of merging that it doesn't merge properly

such as Example:

mergesort.in: // all number is one array and not use temp array for sorting

2 //-->This is Array Number
5 //-->This is Array(next line) Length
4 6 98 8 24
8 //-->This is Array(next line) Length
12 14 89 21 4 7 9 41

mergesort.Out:

  //Output in file mergesort.Out

4 6 8 24 98
4 7 9 12 14 21 41 89

I'm not understand how to work mergeArray function for in-place merge Sort

    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication1
    {
        class ReadFromFile
        {
            static void Main()
            {
                ArrayList lines = new ArrayList();

            var input = System.IO.File.ReadAllLines(@"C:\mergesort.in");

            System.Console.WriteLine("Contents of mergesort.in = ");

            foreach (string line in input)
            {
                Console.WriteLine("\t" + line);
            }
            foreach (var i in input)
            {
                if (Convert.ToInt32(i.Length) > 1)
                {
                    var counter = 0;
                    foreach (var item in input)
                    {
                        if (input[counter].Length > 1)
                        {
                            string[] t = input[counter].Split(' ');
                            foreach (string word in t)
                            {
                                lines.Add(word);
                            }
                            ReadFromFile.mergesort(t, 0, 5, lines);
                        }
                        counter++;
                    }

                    foreach (string line in lines)
                    {
                        Console.WriteLine("\t" + line);
                    }
                    break;
                }
            }

            Console.WriteLine("Press any key to exit...");
            System.Console.ReadKey();
        }

        private static void mergesort(string[] t, int p1, int p2, ArrayList lines)
        {
            if (p1 < p2)
            {
                int mid = (p2 + p1) / 2;
                ReadFromFile.mergesort(t, p1, mid, lines);
                Console.WriteLine(p1);

                ReadFromFile.mergesort(t, mid + 1, p2, lines);
                Console.WriteLine(t);
                foreach (var item in t)
                {
                    Console.WriteLine(item);
                }
                ReadFromFile.mergeArray(t, p1, mid, p2, lines);
            }
        }

        private static void mergeArray(string[] arr, int start, int mid, int end, ArrayList lines)
        {

            //I'm not understand how to work this function for in-place merge Sort

        }
    }
}

I'm not really understand what you want to do... what with 2, 5 - where them are in your output ? why you divide the output to two groups? please give more details... — AsfK, Jun 24 '14 at 12:48
and of course you can found stuff about mergesort on the web, link1: http://en.wikipedia.org/wiki/Merge_sort link2: http://www.sorting-algorithms.com/merge-sort — AsfK, Jun 24 '14 at 12:50
Merge sorting an array in-place is possible, but difficult. I'm pretty sure you don't really want to do that. See http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm for reasons why. — Jim Mischel, Jun 24 '14 at 14:10
@AsfK add more comments in original content and 2 in array number and 5 in next array Length — mail temp, Jun 24 '14 at 14:38
@JimMischel i see this post and not answer my Question(& I'm don't understand). Thank you for add commnet. — mail temp, Jun 24 '14 at 14:43
What is your question? If you're asking how to do in-place merge, then my suggestion is that you not try it. That's the point of the link I provided. Merge sort typically requires a secondary array, which is what I suggest you use. — Jim Mischel, Jun 24 '14 at 15:36
I want code for C# language and i don't understand linked. what do I fix "mergeArray" Function. Thank you. — mail temp, Jun 24 '14 at 18:50
Do you really want an in place merge sort, or just to return the sorted data in the same array? — Pete Kirkham, Jun 24 '14 at 19:44
Then read Katajainen's paper (AsfK's link) and work it out. There isn't an answer that can be written here without months of effort, and you haven't justified why you need an in-place sort. — Pete Kirkham, Jun 24 '14 at 21:22

score -4 · Answer 1 · answered Jun 24 '14 at 12:52

It would be much easier if you use Linq:

foreach (var line in input)
{
    var elements = line.Split(' ');

    if (elements.Count > 1)
    {
        var t = elements
            .Select(i => Convert.ToInt32(i))
            .Distinct()
            .OrderBy(i => i)
            .Select(i => i.ToString())
            .ToArray();

        Console.WriteLine("\t" + string.Join(" ", t));
    }
}

Use .Union if you want to merge unique values from more than one array

This question is about the mergesort algorithm. – JLRishe Jun 24 '14 at 12:59 — JLRishe, Jun 24 '14 at 12:59

in-place Merge Sort | C#

1 Answers1