Merge Sort in MATLAB | MATLAB Tutorial

Merge Sort in MATLAB | MATLAB Tutorial
  • 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.

 

Example:

 

 

 

  • 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.

 

Matlab Code:

Function:

 
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

Test Code:

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')

Simulation Results:

 

 

  • 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.

Time Complexity:

    • Best Case: O (nlogn)
    • Worst Case: O (nlogn)
    • Average Case: O (nlogn)

Experienced Programmer skilled in Machine Learning, MATLAB, Java, MySQL, and MongoDB. Strong engineering professional persuing a Bachelor’s Degree focused in Information and Communication Technology from School of Engineering & Applied Sciences, Ahmedabad University.