Merge Sort in MATLAB | MATLAB Tutorial
by Ratnesh Shah
- Merge Sort is a sorting algorithm based on divide and conquer paradigm.
- Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.
- It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[1..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
- At every iteration the problem is subdivided into two parts and so the size of the problem is reduced to two halves. And at each iteration some work is done in merging and separation.
- Therefore, the recurrence for merge sort running time is,
T (n) = θ (n) if n = 1,
= 2 T (n/2) + θ (n) if n > 1.
function list = mergeSort(list) if numel(list) <= 1 return else middle = ceil(numel(list) / 2); left = list(1:middle); right = list(middle+1:end); left = mergeSort(left); right = mergeSort(right); if left(end) <= right(1) list = [left right]; return end %merge(left,right) counter = 1; while (numel(left) > 0) && (numel(right) > 0) if(left(1) <= right(1)) list(counter) = left(1); left(1) = ; else list(counter) = right(1); right(1) = ; end counter = counter + 1; end if numel(left) > 0 list(counter:end) = left; elseif numel(right) > 0 list(counter:end) = right; end %end merge end %if end %mergeSort
i=1; k = 1:100:10000; val = zeros(1,length(j)); for j = 1:100:10000 %array size R = randn([1 j]); %generating array of size j containing random elements tic; %starting the timer P = mergeSort(R);%calling the merge sort function end plot(k,val); %plotting array size vs time taken for sorting using Merge sort algorithm grid on; xlabel('array length'); ylabel('Time Taken in seconds'); title('Analysis Plot'); legend('Merge Sort')
- The above plot is similar to that of function (nlogn). Thus the time complexity of the merge sort algorithm is O (nlogn).
- This can also be proved using Recurrence Tree method:
Advantages of Merge Sort:
Merge sort is better in terms of time complexity in comparison to other sorting algorithms such as insertion sort, selection sort and bubble sort and also sometimes better than quick sort.
- Best Case: O (nlogn)
- Worst Case: O (nlogn)
- Average Case: O (nlogn)