merge sort Algorithm

Merge sort is a highly efficient, stable, and comparison-based sorting algorithm that employs the divide and conquer strategy. It works by recursively dividing the unsorted array or list into two equal halves, sorting each half individually, and then merging them back together into a single sorted array. This process of dividing, sorting, and merging continues until the entire array is sorted. The primary advantage of merge sort is its ability to handle large data sets with a time complexity of O(n log n), making it significantly faster than many other sorting algorithms, such as bubble sort and insertion sort. The merge sort algorithm begins by dividing the input array into two halves. Each half is then sorted recursively using the same merge sort algorithm. Once both halves are sorted, they are combined or merged back together in a manner that maintains their sorted order. This merging process involves iterating through each element in the two halves and comparing them, selecting the smaller element and placing it in the sorted array. This comparison and selection process continues until all elements from both halves have been placed in the sorted array. The merge step is a crucial aspect of the merge sort algorithm, as it ensures that the combined array remains sorted. The process of dividing, sorting, and merging is repeated until the entire array is sorted, resulting in a highly efficient and reliable sorting algorithm that is particularly well-suited for handling large data sets.
%% Merge sorting Algorithm:
function y = merge_sort(x)
% function to sort vector 'x' with using the merge sort algorithm
% INPUT: 'x' array
% OUTPUT: sorted array
n = length(x);
if n==1
    y = x;
else
    m = floor(n/2);
    left = merge_sort(x(1:m))    % sorting left part of vector
    right = merge_sort(x(m+1:n)) % sorting right part of vector
    y = merge(left,right)        % with using 'merge' function, 2 part will be merged
end

%% Merge Algorithm:
function z = merge(x,y)
n = length(x); m = length(y); z = zeros(1,n+m);
ix = 1; 
iy = 1; 
for iz=1:(n+m)
    % Deteremin the iz-th value for the merged array.
    if ix > n
        % All done with x-values. Select the next y-value.
        z(iz) = y(iy); iy = iy+1;
    elseif iy > m
        % All done with y-values. Select the next x-value.
        z(iz) = x(ix); ix = ix + 1;
    elseif x(ix) <= y(iy)
        % The next x-value is less than or equal to the next y-value
        z(iz) = x(ix); ix = ix + 1;
    else
        % The next y-value is less than the next x-value
        z(iz) = y(iy); iy = iy + 1;
    end
end

LANGUAGE:

DARK MODE: