Complete the C# Merge-Sort Program by completing the methods in this program. This program consists of two parts:

1. Main - which runs the entire program.

2. LinkedNode - LinkedNode is a class containing methods to preform Merge-Sort. The goal is to complete these methods These Methods are:

- Sort

-SortFromList

-AddLast

-AddFirst

-InsertAfter

-InsertBefore

- Find

-SetNext

-PrintList

These functions are used in larger functions called:

- DoMergeSort

- SplitList

- MergeLists

- SwapNodes

Algorithms written in C are provided for the Merge, doMerge, and SwapNodes methods

Below is the code for main()

public static void Main(string[] args) { Console.WriteLine("Hello Merge Sort World!"); LinkNode head = new LinkNode(10); LinkNode lastNode = head; Random rnd = new Random(DateTime.Now.Millisecond); for (int i = 1000; i >= 1; i--) { lastNode = lastNode.AddLast(rnd.Next(0, 200)); } // print elements in the list Console.WriteLine("*** Origional List ***"); head.PrintList(); // sort the list Console.WriteLine("Performing Sort..."); Console.WriteLine(""); head = head.Sort(); // now, list should be sorted... Console.WriteLine("*** Sorted List ***"); foreach (int val in head) { Console.WriteLine(val); } }

Next, this is the code for the LinkedNode Class This is the where the methods are that need to be completed:

using System; using System.Collections.Generic; using System.IO; using System.Linq; namespace MergeSort { public class LinkNode { public LinkNode(T value = default(T), LinkNode next = null, LinkNode previous = null) { Value = value; Next = next; previous = Previous; // Next { get; protected set; } public LinkNode Previous { get; protected set; } ///

/// Sorts list starting from this node, /// returns new head of the list. ///

/// The sort. public LinkNode Sort() { LinkNode head = this; DoMergeSort(ref head); return head; } public LinkNode SortFromFirst() { //todo: get head of the list, // then sort from there. } public LinkNode AddLast(T) { //TODO: add new element at the end of the list, //and return the new node as a result. // (you must walk the list to the tail, and insert after) }

public LinkNode AddFirst(T) { //TODO: add new element at the beginning of the list, //and return the new node as a result. // Note that you are changing the head of the list // (you must walk the list to the head, and insert before) } public LinkNode InsertAfter(T) { //TODO: insert element between this node and the next, //and return the new node as a result. } public LinkNode InsertBefore(T) { //TODO: insert element between this node and previous node, //and return the new node as a result. } public LinkNode Find(T) { //TODO: // Ability to find an element in the list // If it doesnt exist, return null. // Think about how you need to do this } ///

/// Performs merge sort, starting from the list head ///

/// Head. public static void DoMergeSort(ref LinkNode head) { //TODO } public static void SplitList(LinkNode head, ref LinkNode h1, ref LinkNode h2) { //TODO! } public static LinkNode MergeLists(LinkNode headA, LinkNode headB) { //TODO! } public void SetNext(LinkNode node) { Next = node; } public void PrintList() { } } }

Merge code algorithm in C:

void doMergeSort(contact **head, int sortBy, int sortOrder); void splitList (contact *head, contact **h1, contact **h2); contact *mergeLists(contact *l1, contact *l2); void swapNodes(contact **node1, contact **node2);

doMergeSort algorithm in C:

void doMergeSort(contact **head, int sortBy, int sortOrder) { // do not process empty or single-node list if (head==NULL || *head == NULL || (*head)->next==NULL) return; contact *first, *second; // split the list in half splitList(*head, &first, &second); // perform recursive merge sort on both halves doMergeSort(&first, sortBy, sortOrder); doMergeSort(&second, sortBy, sortOrder); // Merge both halves back together, // sorting as indicated by sortBy and sortOrder. if (sortBy==0) *head = mergeListsByLastName(first, second, sortOrder); else *head = mergeListsByFirstName(first, second, sortOrder);

swapNodes algorithm in C:

void splitList (contact *head, contact **h1, contact **h2) { *h1 = head; *h2 = NULL; contact *low = head; contact *high = head->next; // find where split will happen... while (high) { high = high->next; if (high==NULL) break; high = high->next; low = low->next; } //assign second half to h2 *h2 = low->next; // chop first half by setting next member to NULL low->next=NULL; } contact *mergeLists (contact *l1, contact*l2) { // setup our "control" variables contact *head = NULL; contact **lastRef = &head; while (1) // while TRUE... { if (l1==NULL || l2==NULL) { *lastRef = l1?l1:l2; break; } // do comparison here. if (strcmp(l1->lastName,l2->lastName)next); } return head; } void swapNodes(contact **node1, contact **node2) { contact *src = *node1; *node1 = (*node1)->next; src->next = *node2; *node2 = src; }

Here is a diagram showing the Merge-Sort Algorithm:

Sort Linked list. > NULL Divide Phase. 40-20-60 - 1060|| 30 NULL O NULL In this Phase, Linked list is divided until size of list is 1. NULL > NULL NULL | 40 --> NULL 20 ->NULI 10->NULL 50 NULL Sort (40) and (20) Sort (10) and (50) Conquer Phase. + 40 + NULL In this Phase, divided linked list is sorted by comparing them one by one and sorted list is passed further. 10 500 -NULL 1030 E 60 E > NULL Sort (20, 40) and (60) Sort (10, 50) and (30) 201 - 40-60 +-nu Sort (20, 40, 60) and (10, 30, 50) 10-200 - 406000 + NULL