123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
// Function to merge two sorted halves of the array
void merge(vector<int> &arr, int low, int mid, int high) {
// Temporary array to store merged elements
vector<int> temp;
int left = low;
int right = mid + 1;
// Loop until subarrays are exhausted
while (left <= mid && right <= high) {
// Compare left and right elements
if (arr[left] <= arr[right]) {
// Add left element to temp
temp.push_back(arr[left]);
// Move left pointer
left++;
}
else {
// Add right element to temp
temp.push_back(arr[right]);
// Move right pointer
right++;
}
}
// Adding the remaining elements of left half
while (left <= mid) {
temp.push_back(arr[left]);
left++;
}
// Adding the remaining elements of right half
while (right <= high) {
temp.push_back(arr[right]);
right++;
}
// Transferring the sorted elements to arr
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
// Helper function to perform merge sort from low to high
void mergeSortHelper(vector<int> &arr, int low, int high){
// Base case: if the array has only one element
if (low >= high)
return;
// Find the middle index
int mid = (low + high) / 2;
// Recursively sort the left half
mergeSortHelper(arr, low, mid);
// Recursively sort the right half
mergeSortHelper(arr, mid + 1, high);
// Merge the sorted halves
merge(arr, low, mid, high);
}
// Function to perform merge sort on the given array
vector<int> mergeSort(vector<int> &nums) {
int n = nums.size(); // SIze of array
// Perform Merge sort on the whole array
mergeSortHelper(nums, 0, n-1);
// Return the sorted array
return nums;
}
};
int main(){
vector<int> arr = {9, 4, 7, 6, 3, 1, 5};
int n = arr.size();
cout << "Before Sorting Array: " << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
// Create an instance of the Solution class
Solution sol;
// Function call to sort the array
vector<int> sortedArr = sol.mergeSort(arr);
cout << "After Sorting Array: " << endl;
for (int i = 0; i < n; i++)
cout << sortedArr[i] << " ";
cout << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
import java.util.*;
class Solution {
// Function to merge two sorted halves of the array
public void merge(int[] arr, int low, int mid, int high) {
// Temporary array to store merged elements
List<Integer> temp = new ArrayList<>();
int left = low;
int right = mid + 1;
// Loop until subarrays are exhausted
while (left <= mid && right <= high) {
// Compare left and right elements
if (arr[left] <= arr[right]) {
// Add left element to temp
temp.add(arr[left]);
// Move left pointer
left++;
} else {
// Add right element to temp
temp.add(arr[right]);
// Move right pointer
right++;
}
}
// Adding the remaining elements of left half
while (left <= mid) {
temp.add(arr[left]);
left++;
}
// Adding the remaining elements of right half
while (right <= high) {
temp.add(arr[right]);
right++;
}
// Transferring the sorted elements to arr
for (int i = low; i <= high; i++) {
arr[i] = temp.get(i - low);
}
}
// Helper function to perform merge sort from low to high
public void mergeSortHelper(int[] arr, int low, int high) {
// Base case: if the array has only one element
if (low >= high)
return;
// Find the middle index
int mid = (low + high) / 2;
// Recursively sort the left half
mergeSortHelper(arr, low, mid);
// Recursively sort the right half
mergeSortHelper(arr, mid + 1, high);
// Merge the sorted halves
merge(arr, low, mid, high);
}
// Function to perform merge sort on the given array
public int[] mergeSort(int[] nums) {
int n = nums.length; // Size of array
// Perform Merge sort on the whole array
mergeSortHelper(nums, 0, n - 1);
// Return the sorted array
return nums;
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {9, 4, 7, 6, 3, 1, 5};
int n = arr.length;
System.out.println("Before Sorting Array: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
// Create an instance of the Solution class
Solution sol = new Solution();
// Function call to sort the array
int[] sortedArr = sol.mergeSort(arr);
System.out.println("After Sorting Array: ");
for (int i = 0; i < n; i++)
System.out.print(sortedArr[i] + " ");
System.out.println();
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
class Solution:
# Function to merge two sorted halves of the array
def merge(self, arr, low, mid, high):
# Temporary array to store merged elements
temp = []
left = low
right = mid + 1
# Loop until subarrays are exhausted
while left <= mid and right <= high:
# Compare left and right elements
if arr[left] <= arr[right]:
# Add left element to temp
temp.append(arr[left])
# Move left pointer
left += 1
else:
# Add right element to temp
temp.append(arr[right])
# Move right pointer
right += 1
# Adding the remaining elements of left half
while left <= mid:
temp.append(arr[left])
left += 1
# Adding the remaining elements of right half
while right <= high:
temp.append(arr[right])
right += 1
# Transferring the sorted elements to arr
for i in range(low, high + 1):
arr[i] = temp[i - low]
# Helper function to perform merge sort from low to high
def mergeSortHelper(self, arr, low, high):
# Base case: if the array has only one element
if low >= high:
return
# Find the middle index
mid = (low + high) // 2
# Recursively sort the left half
self.mergeSortHelper(arr, low, mid)
# Recursively sort the right half
self.mergeSortHelper(arr, mid + 1, high)
# Merge the sorted halves
self.merge(arr, low, mid, high)
# Function to perform merge sort on the given array
def mergeSort(self, nums):
n = len(nums) # Size of array
# Perform Merge sort on the whole array
self.mergeSortHelper(nums, 0, n - 1)
# Return the sorted array
return nums
if __name__ == "__main__":
arr = [9, 4, 7, 6, 3, 1, 5]
n = len(arr)
print("Before Sorting Array: ")
for i in range(n):
print(arr[i], end=" ")
print()
# Create an instance of the Solution class
sol = Solution()
# Function call to sort the array
sortedArr = sol.mergeSort(arr)
print("After Sorting Array: ")
for i in range(n):
print(sortedArr[i], end=" ")
print()
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
class Solution {
// Function to merge two sorted halves of the array
merge(arr, low, mid, high) {
// Temporary array to store merged elements
let temp = [];
let left = low;
let right = mid + 1;
// Loop until subarrays are exhausted
while (left <= mid && right <= high) {
// Compare left and right elements
if (arr[left] <= arr[right]) {
// Add left element to temp
temp.push(arr[left]);
// Move left pointer
left++;
} else {
// Add right element to temp
temp.push(arr[right]);
// Move right pointer
right++;
}
}
// Adding the remaining elements of left half
while (left <= mid) {
temp.push(arr[left]);
left++;
}
// Adding the remaining elements of right half
while (right <= high) {
temp.push(arr[right]);
right++;
}
// Transferring the sorted elements to arr
for (let i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
// Helper function to perform merge sort from low to high
mergeSortHelper(arr, low, high) {
// Base case: if the array has only one element
if (low >= high)
return;
// Find the middle index
let mid = Math.floor((low + high) / 2);
// Recursively sort the left half
this.mergeSortHelper(arr, low, mid);
// Recursively sort the right half
this.mergeSortHelper(arr, mid + 1, high);
// Merge the sorted halves
this.merge(arr, low, mid, high);
}
// Function to perform merge sort on the given array
mergeSort(nums) {
let n = nums.length; // Size of array
// Perform Merge sort on the whole array
this.mergeSortHelper(nums, 0, n - 1);
// Return the sorted array
return nums;
}
}
const main = () => {
let arr = [9, 4, 7, 6, 3, 1, 5];
let n = arr.length;
console.log("Before Sorting Array: ");
for (let i = 0; i < n; i++)
process.stdout.write(arr[i] + " ");
console.log();
// Create an instance of the Solution class
let sol = new Solution();
// Function call to sort the array
let sortedArr = sol.mergeSort(arr);
console.log("After Sorting Array: ");
for (let i = 0; i < n; i++)
process.stdout.write(sortedArr[i] + " ");
console.log();
}
// Execute the main function
main();
