Merge Sort | For Beginners | Java Placement Course
Divide the unsorted array into two halves, mid and left.
Sort the left half recursively using merge sort algorithm.
Sort the right half recursively using merge sort algorithm.
Merge the two sorted halves to obtain the final sorted array.
JAVA Implementation:
// Merge sort
public class MergeSort{
//time complexity=nlogn
public static void conquer(int arr[], int si, int mid, int ei ) {
int merged[] = new int[ei - si + 1];
int idx1 = si;
int idx2 = mid+1;
int x = 0;
//time complexity=O(n)
while(idx1 <= mid && idx2 <= ei){
if(arr[idx1] <= arr[idx2]){
merged[x++] = arr[idx1++];
}
else {
merged[x++] = arr[idx2++];
}
}
while(idx1 <= mid){
merged[x++] = arr[idx1++];
}
while(idx2 <= ei){
merged[x++] = arr[idx2++];
}
for(int i=0, j=si; i<merged.length; i++, j++){
arr[j] = merged[i];
}
}
public static void divide( int arr[], int si, int ei) {
if (si >= ei) {
return;
}
//time complexity=O(logn)
int mid = si + (ei - si)/2;
divide(arr, si, mid);
divide(arr, mid+1, ei);
conquer(arr, si, mid, ei);
}
public static void main(String[] args) {
int arr[] = {6,3,9,5,2,8};
int n = arr.length;
// divide
divide(arr, 0, n-1);
//print
for(int i=0; i<n; i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
Rule :- Divide and Conquer Rule
-------------------------------------------------
C Implementation:
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
int i = 0, j = 0, k = 0;
while (i < left_size && j < right_size) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left_size) {
arr[k++] = left[i++];
}
while (j < right_size) {
arr[k++] = right[j++];
}
}
void merge_sort(int arr[], int size) {
if (size < 2) {
return;
}
int mid = size / 2;
int* left = (int*) malloc(mid * sizeof(int));
int* right = (int*) malloc((size - mid) * sizeof(int));
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
merge_sort(left, mid);
merge_sort(right, size - mid);
merge(arr, left, mid, right, size - mid);
free(left);
free(right);
}
int main() {
int arr[] = {5, 2, 8, 4, 7, 1, 3, 6};
int size = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, size);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
In this C implementation, the "merge_sort" function takes an array and its size as input, and sorts the array in place using the merge function. The merge function takes two sorted arrays (left and right) and their sizes, and merges them into a single sorted array ('arr').
C++ Implementation:
Step 1: Create a function to merge two arrays
//c
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
This function takes an array, a left index, a middle index, and a right index as parameters. It first creates two temporary arrays to store the left and right halves of the original array. It then compares the elements of the left and right arrays and merges them back into the original array in sorted order.
Step 2: Create a function to divide the array into halves and call the merge function
//c
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Step 3: Call the mergeSort function on the array to be sorted
// c
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Python Implementation:
// python
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Divide the array into two halves
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort the two halves
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# Merge the two sorted halves
result = []
i = 0
j = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
result.append(left_half[i])
i += 1
else:
result.append(right_half[j])
j += 1
result += left_half[i:]
result += right_half[j:]
return result
Let's break down this implementation step by step:
The merge_sort function takes an array arr as input and returns a sorted version of the array.
The function checks if the length of the array is less than or equal to 1. If it is, the array is already sorted, so the function simply returns the array.
If the length of the array is greater than 1, the function divides the array into two halves using integer division (//). It then recursively calls itself on each half to sort them.
Once the two halves are sorted, the function merges them back together by comparing the first elements of each half and adding the smaller one to the result array. It continues this process until one of the halves is empty, at which point it simply adds the remaining elements from the other half to the result array.
Finally, the function returns the sorted result array.
Let's try running the merge_sort function on an example array:
// python
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
As you can see, the function correctly sorts the array in ascending order. I hope this explanation and example help you understand how Merge Sort works in Python!
OTHERS BLOG'S:-
>> Enter 3 numbers from the user & make a function to print their average in java, c++, python, java.
Comments
Post a Comment