hi👋Devs,
I hope you getting some things from this Sorting Algorithms series.
in this article, we will discuss the very efficient and fast algorithm, Merge Sort algorithms.
Merge Sort
Merge Sort algorithm is based on the divide & conquer principle which states that repeatedly breaks down the problem into sub-problem, solves each sub-problem individually, and combines the sub-problem solutions into a final solution.
Let's understand this algorithm in a much better way with an example.
step-1 find the mid point and recursively divide the array into two subarrays until the array size becomes 1.
step-2 merge the two subarrays into an array till the final array is merged, in ascending order.
Pseudocode for recursively divide the array into two sub-arrays.
step-1 initialise left & right index of an array.
step-2 return if array size is 1.
if left >= right return.
step-3 find the mid of the array.
mid = (left + right) / 2
step-4 divide the array into two sub-array.
divide( array, left, mid)
divide( array, mid+1, right)
step-5 merge the two sub-array into a array.
marge( array, left, mid, right)
Pseudocode for merge the two sub-arrays.
step-1 calculate the size of left & right sub-arrays.
leftArrSize = mid - left+1
rightArrSize = right - mid
step-2 initialise the temps arrays for left & right sub-arrays
leftArr[]
rightArr[]
step-3 copy sub-arrays into the temp arrays.
leftArr[] = array[left....mid]
rightArr[] = array[mid+1...right]
step-4 set initial indexes of subarrays & array.
leftPointer = 0
rightPointer = 0
arrPointer = left
step-5 copy the temp sub-arrays into an array, in ascending or descending order, till the end of any temp sub-arrays.
step-6 copy the remaining elements of temp sub-arrays.
see the java implementation
Java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{5,9,2,7,1,10,4,1,50};
System.out.println("unsorted Array : "+Arrays.toString(arr));
mergeSort(arr,0,arr.length-1);
System.out.println("sorted Array in ascending order : "+Arrays.toString(arr));
}
private static void mergeSort(int[] arr,int left,int right){
// return if arr size becomes 1
if(left >= right) return;
// calculate the mid
int mid = ( left + right ) / 2;
// divide the array into two subarrays
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
// merge subarrays
merge(arr,left,mid,right);
}
private static void merge(int[] arr,int left,int mid,int right){
// calculate the size of left & right subarrays
int leftArrSize = mid - left+1;
int rightArrSize = right - mid;
// initialise temp subarrays
int[] leftArr = new int[leftArrSize];
int[] rightArr = new int[rightArrSize];
// copy left & right array into temp arrays
for (int i = 0; i < leftArrSize; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < rightArrSize; ++j)
rightArr[j] = arr[mid + 1 + j];
// set initial indexes of subarrays
int leftPointer = 0;
int rightPointer = 0;
int arrPointer = left;
// copy temp subarrays, in ascending order
while(leftPointer < leftArrSize && rightPointer < rightArrSize ){
if(leftArr[leftPointer] <= rightArr[rightPointer]){
arr[arrPointer] = leftArr[leftPointer];
arrPointer++;
leftPointer++;
}else{
arr[arrPointer] = rightArr[rightPointer];
arrPointer++;
rightPointer++;
}
}
// copy the remaining elements of left subarray into a marge array
while(leftPointer < leftArrSize){
arr[arrPointer] = leftArr[leftPointer];
arrPointer++;
leftPointer++;
}
// copy the remaining elements of right subarray into a merge array
while(rightPointer < rightArrSize){
arr[arrPointer] = rightArr[rightPointer];
arrPointer++;
rightPointer++;
}
}
}
Thank you for reading this article. share this article with your dev friends and save it for the future.
Top comments (0)