# Merge Sort in MATLAB | MATLAB Tutorial

###### byRatnesh 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.

## 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:

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)

##### Ratnesh Shah

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.

### Recommended Posts

##### Test Post

17 Feb 2018 - Tutorial

##### Counters using conditionally executed subsystems | Simulink Tutorial

16 Feb 2018 - Simulink, Tutorial

##### Regulating drum boiler pressure

16 Feb 2018 - Simulink, Tutorial