Implement INSERTION-SORT and MERGE-SORT in the programming language of your choi

Question

Implement INSERTION-SORT and MERGE-SORT in the programming language of your choice. Determine experimentally the largest value of n (number of elements in the sequence to be sorted) for which INSERTION-SORT is still faster than MERGE-SORT.

Now modify your code for MERGE-SORT such that it calls INSERTION-SORT as a subroutine for input sizes not greater than the value determined by experiment.

Draw a diagram that shows the running times of INSERTION-SORT, MERGE-SORT and the hybrid INSERTION-MERGE-SORT algorithm for various input sizes n. You should perform all your experiments on the same machine and using the same programming language. Since the actual running time depends on the input sequence, use several random input sequences to produce an average running time for each value of n tested.

Briefly describe the observed behavior of the three algorithms for values of n both smaller and larger than the cross-over value determined experimentally. Also hand in a printed copy of the code used in the experiments.

Note:

You may use the system time to measure the running time of an algorithm with high precision (up to milliseconds). See http://www.codersource.net/c/c-tutorials/c-date-and-time.aspx for details on how to do this in C++. The function below returns the current time in milliseconds.



int time_s()

{//computes system time in milliseconds

SYSTEMTIME st;

GetSystemTime(&st);

int time1 = (st.wHour*60*60*1000) + (st.wMinute*60*1000) + (st.wSecond*1000) + (st.wMilliseconds);

return time1;

}

Explanation / Answer

INSERT SORT IN C struct LIST { struct LIST * pNext; int iValue; }; struct LIST * SortList(struct LIST * pList) { /* build up the sorted array from the empty list */ struct LIST * pSorted = NULL; /* take items off the input list one by one until empty */ while (pList != NULL) { /* remember the head */ struct LIST * pHead = pList; /* trailing pointer for efficient splice */ struct LIST ** ppTrail = &pSorted; /* pop head off list */ pList = pList->pNext; /* splice head into sorted list at proper place */ while (TRUE) { /* does head belong here? */ if (*ppTrail == NULL || pHead->iValue < *ppTrail->iValue) { /* yes */ pHead->pNext = *ppTrail; *ppTrail = pHead; break; } else { /* no - continue down the list */ ppTrail = & (*ppTrail)->pNext; } } } return pSorted; } MERGE SORT IN C function merge_sort(m) if length(m) = 1 return m var list left, right, result var integer middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after or equal middle add x to right left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result The merge function needs to then merge both the left and right lists. It has several variations; one is shown: function merge(left,right) var list result while length(left) > 0 or length(right) > 0 if length(left) > 0 and length(right) > 0 if first(left) = first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) else if length(left) > 0 append first(left) to result left = rest(left) else if length(right) > 0 append first(right) to result right = rest(right) end while return result

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.