---

CIS 3223 Lab02 – Merge Sort Algorithm

DUE: (before the next lab, 10:30am Friday, Feb 8, 2008)

---

TASKS

1. Implement in Matlab the Merge Sort algorithm whose pseudocode was covered in class. You should do it by writing the function:

function sorted_array = merge_sort(original_array)

that takes original_array as input and produces sorted_array as output. Submit the Matlab code you wrote.

2. Run the algorithm on a randomly generated arrays of size N = {5, 10, 100, 1000, 10000, 100000, 1000000} and record the time it takes to do the sorting (you can use the tic and toc Matlab functions to measure elapsed time). You can do it as:

N = 100;

original_array = rand(N,1);

tic

sorted_array = merge_sort(original_array);

elapsed_time = toc

3. Repeat the experiments, but this time use already sorted arrays of size N = {5, 10, 100, 1000, 10000, 100000, 1000000} and record the time it takes to do the sorting. You can do it as:

N = 100;

original_array = rand(N,1);

sorted_array = merge_sort(original_array);

tic

sorted_array = merge_sort(sorted_array);

elapsed_time = toc

Submit the tables summarizing the elapsed times in both types of experiments. Discuss the results and explain how the elapsed time changes as a function of N (e.g., linearly, quadratically, exponentially). Compare the results with those of Insertion Sort obtained in Lab 1.

4. Repeat Tasks 2 and 3, but this time use Matlab’s built-in sort function. Compare the results with those of Insertion Sort and Merge Sort algorithms. How does the sort function scale with array size?