Instantly share code, notes, and snippets.

# mycodeschool/MergeSort_C.C

Last active July 2, 2024 12:39
Show Gist options
• Save mycodeschool/9678029 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* Merge sort in C */ #include #include // Function to Merge Arrays L and R into A. // lefCount = number of elements in L // rightCount = number of elements in R. void Merge(int *A,int *L,int leftCount,int *R,int rightCount) { int i,j,k; // i - to mark the index of left aubarray (L) // j - to mark the index of right sub-raay (R) // k - to mark the index of merged subarray (A) i = 0; j = 0; k =0; while(i

Thanks alot sir, best explanation on internet.

Python implementation, did variables with much wordings for a simpler follow-along,

``````def mergeSort(array):
arrayLength = len(array)
if arrayLength<2:
return
#cmpute array mid-point
mid = arrayLength//2

# create two lists/array and initialize with default values
leftArray= list(range(mid))
rightArray= list(range(arrayLength-mid))

# populate the two arrays with values from original array/list
for idx in range(mid):
leftArray[idx] = array[idx]
for idx in range(mid, arrayLength):
rightArray[idx-mid] = array[idx]

# call a mergeSort method recursively until the base case of len <2 is reached
# means one element is remaining in a given list
mergeSort(leftArray)
mergeSort(rightArray)

#then start merging picking left and right array from call stack
merge(leftArray,rightArray,array)

# meged array
return array

def merge(leftArray,rightArray,array):
leftArrayLength = len(leftArray)
rightArrayLength = len(rightArray)

leftIdx=rightIdx=arrayIdx=0

# loop until the len of either array
while(leftIdx < leftArrayLength and rightIdx < rightArrayLength):
if leftArray[leftIdx] <= rightArray[rightIdx]:
array[arrayIdx] = leftArray[leftIdx]
leftIdx +=1
else:
array[arrayIdx] = rightArray[rightIdx]
rightIdx +=1
arrayIdx +=1

# case when right array is exhausted before the left one
while leftIdx < leftArrayLength:
array[arrayIdx] = leftArray[leftIdx]
leftIdx +=1
arrayIdx +=1

# case when left array is exhausted before the left one
while rightIdx < rightArrayLength:
array[arrayIdx] = rightArray[rightIdx]
rightIdx +=1
arrayIdx +=1

# tests
testArray =[6,2,3,1,9,10,15,13,12,17]
expected = [1, 2, 3, 6, 9, 10, 12, 13, 15, 17]

assert mergeSort(testArray) == expected
``````

### row-star-134 commented Sep 13, 2021

Merge sort in java

`class mergeSortAlgorithms{

public void merge(int arr[], int start , int mid , int end){

``````//find the size of right and left halves
int n1 = mid - start +1;
int n2 = end - mid;

//make the temporary array equal to right and left halve
int left[] = new int[n1];
int right[] =  new int[n2];

//fill the right and left halves
for(int i=0;i<n1;i++){
left[i] = arr[i+start];
}
for(int j=0;j<n2;j++){
right[j] = arr[mid+1+j];
}
//intialize variable
int i = 0 ,j=0, k = start;

//sort the array
while(i<n1 && j <n2){

if(left[i] < right[j]){
arr[k] = left[i];
i++;
}
else{
arr[k] = right[j];
j++;
}
k++;
}
//copying the reamaining value of right and left halves
while(i<n1){
arr[k] =left[i];
i++;
k++;
}
while(j<n2){
arr[k] = right[j];
j++;
k++;
}
``````

}
public void mergeSort(int arr[], int start ,int end){
//check if start greater than end
if(start < end){
int mid = (start+end)/2;

``````  //divide into two halves recursively
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);

//merge into two halves
merge(arr,start,mid,end);
}
``````

}
public static void main(String[] args) {
//random array
int arr[] = {25,20,4,24};

``````//object of same class
mergeSortAlgorithms array = new mergeSortAlgorithms();
//call the mergesort function
array.mergeSort(arr,0,arr.length-1);
//display sorted array
for (int i=0;i<arr.length ;i++ ) {
System.out.println(arr[i]);
}
``````

}
}

`

To compile and run online same program : click on this link :
https://debuggingsolution.blogspot.com/2021/09/mergesort.html

i did the array split in 1 loop

``````for(i = 0;i<mid;i++){
L[i] = A[i];
R[i] = A[mid+i];
}
if(n%2)R[i] = A[mid+i];
``````

### darshandodamani commented Jun 15, 2022

I had implemented the Merge sort class for the divide and conquer method. The main method is written different.

public class divideandconquer {
//Implement the sorting algorithm Merge Sort, which you will have to use in the
//algorithm for solving Closest-Points. (25%)
//**************
//Not implemented the sort() function. Instead of that
//Merge sort class
class Merge{
private static int k;
static void mergeSort(ArrayList A, int start, int end) {
//check condition if start greater than end
if(start < end) {
//using a formula
int mid = (start + (end-1)) / 2;
//Now we divide into two valves for multiple times
mergeSort(A, start, mid);
mergeSort(A, mid+1, end);
//merge into two valves
merge(A, start, mid, end);
}
}
public static void merge(ArrayList A, int startpoint, int midpoint, int endpoint ) {
//Calculate the size of left and right halves
int lefthalve = midpoint - startpoint + 1 ;
int righthvalve = endpoint - midpoint ;
//create a temporary sub-arrays and assigned to calculated left halves
int [] left = new int[lefthalve];
//create a temporary sub-arrays and assigned to calculated right halves
int [] right = new int [righthvalve];
//We fill our sorted right sub-arrays into temporaries
for (int leftIndex = 0; leftIndex < lefthalve; ++leftIndex) {
left[leftIndex] = A.get(startpoint+leftIndex);
}
//We fill our sorted left sub-arrays into temporaries
for (int rightIndex = 0; rightIndex < righthvalve; ++rightIndex) {
right[rightIndex] = A.get(midpoint + 1 + rightIndex);
}
//Initialize the variables, iterators containing current index of temp sub-arrays
int leftIndex = 0; int rightIndex = 0; int k=startpoint;
// copying from leftArray and rightArray back into array
//for (int i = start; i < end + 1; i++) {
while(leftIndex < lefthalve && rightIndex < righthvalve) {
if(left[leftIndex]<right[rightIndex]) {
A.set(k, left[leftIndex]);
leftIndex++;
}
else {
A.set(k, right[rightIndex]);
rightIndex++;
}
k++;
}
// if all the elements have been copied from rightArray, copy the rest of leftArray
while (leftIndex < lefthalve) {
A.set(k, left[leftIndex]);
leftIndex++;
k++;
}
// if all the elements have been copied from leftArray, copy the rest of rightArray
while (rightIndex < righthvalve) {
A.set(k, right[rightIndex]);
rightIndex++;
k++;
}
}
//applying getters and setters of defined k value
public static int getK() {
return k;
}
public static void setK(int k) {
Merge.k = k;
}
}
}

thanks