Level 2 | Algorithms | Lab 7
Merge Sort Algorithm
Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It
works by recursively dividing the input array into smaller subarrays and sorting those
subarrays then merging them back together to obtain the sorted array.
Pseudocode for MergeSort
Declare left and right variables which will mark the extreme indices of the array.
Left will be assigned to 0 and right will be assigned to n-1.
Find mid = (left+right)/2.
Call mergeSort on (left,mid) and (mid+1,right).
Above will continue till left<right.
Then we will call merge on the 2 sub-problems.
Merge Sort Algorithm:
MergeSort (arr, left, right):
if left > right
return
mid = (left+right)/2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
end
1|Page
Modern Academy - Eng. Noha Ali
Level 2 | Algorithms | Lab 7
Merge Sort Code:
package mergesort;
public class MergeSort {
public static int [] divide (int[] array)
{
if ([Link] ==1)
return array;
int mid = [Link] / 2;
int [] left = new int [mid];
int [] right= new int [[Link] - mid];
for (int i=0; i< [Link] ; i++)
left[i] = array[i];
for (int i=0; i<[Link] ; i++)
right[i] = array[mid+i];
left = divide(left);
right= divide(right);
return mergeSort(left,right);
}
public static int [] mergeSort (int[] left, int[] right)
{
int[] sortedArr = new int[[Link]+[Link]];
int Rcounter=0 , Lcounter = 0 , counter=0 ;
while (counter < [Link])
{
if (Lcounter < [Link] && Rcounter < [Link])
{
if (left[Lcounter] < right[Rcounter])
{ sortedArr[counter]= left[Lcounter];
Lcounter++;}
else
{ sortedArr[counter]= right[Rcounter];
Rcounter++;}
}
else
{
if (Lcounter == [Link])
{ sortedArr[counter]= right[Rcounter];
Rcounter++;}
else
if (Rcounter == [Link])
{ sortedArr[counter]= left[Lcounter];
Lcounter++;}
}
counter++;
}
return sortedArr;
}
2|Page
Modern Academy - Eng. Noha Ali
Level 2 | Algorithms | Lab 7
public static void main(String[] args) {
int[] array = {8,3,2,9,7,1,5,4};
[Link]("Original array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](array[i] + " ");
}
int sortedArr[]= divide(array);
[Link]("\n Sorted array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](sortedArr[i] + " ");
}
}
}
Another Code:
package mergesort;
public class MergeSort {
public static void mergeSort(int[] array) {
if (array == null || [Link] <= 1) {
return;
}
int[] helper = new int[[Link]];
mergeSort(array, helper, 0, [Link] - 1);
}
private static void mergeSort(int[] array, int[] helper, int low,
int high)
{
if (low < high) {
int middle = (low + high) / 2;
mergeSort(array, helper, low, middle); // Sort left half
mergeSort(array, helper, middle+1,high); //Sort right half
merge(array, helper, low, middle, high); // Merge them
}
}
private static void merge(int[] array, int[] helper, int low, int
middle, int high) {
// Copy both halves into the helper array
for (int i = low; i <= high; i++) {
helper[i] = array[i];
}
int helperLeft = low;
int helperRight = middle + 1;
int current = low;
// Iterate through helper array. Compare the left and right
3|Page
Modern Academy - Eng. Noha Ali
Level 2 | Algorithms | Lab 7
// half, copying back the smaller element from the two halves
// into the original array
while (helperLeft <= middle && helperRight <= high) {
if (helper[helperLeft] <= helper[helperRight]) {
array[current] = helper[helperLeft];
helperLeft++;
} else {
array[current] = helper[helperRight];
helperRight++;
}
current++;
}
// Copy the rest of the left side of the array into the target array
int remaining = middle - helperLeft;
for (int i = 0; i <= remaining; i++) {
array[current + i] = helper[helperLeft + i];
}
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
[Link]("Original array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](array[i] + " ");
}
mergeSort(array);
[Link]("\n Sorted array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](array[i] + " ");
}
}
}
Time Complexity for Merge Sort Algorithm ∈ 𝑶(𝒏 𝑳𝒐𝒈𝒏 ) in the worst case.
4|Page
Modern Academy - Eng. Noha Ali