Answers for "merge sort c"

merge sort c

#include <stdio.h>

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

  int len1 = mid - start + 1;
  int len2 = end - mid;

  int leftArr[len1], rightArr[len2];

  for (int i = 0; i < len1; i++)
    leftArr[i] = arr[start + i];
  for (int j = 0; j < len2; j++)
    rightArr[j] = arr[mid + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = start;

  while (i < len1 && j < len2) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }

  while (j < len2) {
    arr[k] = rightArr[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int start, int end) {
  if (start < end) {

    int mid = start + (end - start) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
  }
}

void display(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);
  
  printf("Original array\n");
  display(arr, size);
  
  mergeSort(arr, 0, size - 1);

  printf("Sorted array\n");
  display(arr, size);
}

merge sort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function merge(list, start, midpoint, end) {
    const left = list.slice(start, midpoint);
    const right = list.slice(midpoint, end);
    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
        if (topLeft >= left.length) {
            list[i] = right[topRight++];
        } else if (topRight >= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] < right[topRight]) {
            list[i] = left[topLeft++];
        } else {
            list[i] = right[topRight++];
        }
    }
}

function mergesort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length;
    }
    if (end - start > 1) {
        const midpoint = ((end + start) / 2) >> 0;
        mergesort(list, start, midpoint);
        mergesort(list, midpoint, end);
        merge(list, start, midpoint, end);
    }
    return list;
}

mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

merge sort algo

def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 # Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
            k+= 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end =" ") 
    print() 
  
# driver code to test the above code 
if __name__ == '__main__': 
    arr = [12, 11, 13, 5, 6, 7]  
    print ("Given array is", end ="\n")  
    printList(arr) 
    mergeSort(arr) 
    print("Sorted array is: ", end ="\n") 
    printList(arr)

merge sort c++

#include "tools.hpp"
/*   >>>>>>>> (Recursive function that sorts a sequence of) <<<<<<<<<<<< 
     >>>>>>>> (numbers in ascending order using the merge function) <<<<                                 */
std::vector<int> sort(size_t start, size_t length, const std::vector<int>& vec)
{
	if(vec.size()==0 ||vec.size() == 1)
	return vec;

	vector<int> left,right; //===>  creating left and right vectors 

	size_t mid_point = vec.size()/2; //===>   midle point between the left vector and the right vector 

	for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);} //===>  left vector 
	for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);} //===>  right vector 

	left = sort(start,mid_point,left); //===>  sorting the left vector 
	right = sort(mid_point,length-mid_point,right);//===>  sorting the right vector 
	

	return merge(left,right); //===>   all the function merge to merge between the left and the right
}
/*

>>>>> (function that merges two sorted vectors of numberss) <<<<<<<<<                                    */ 
vector<int> merge(const vector<int>& a, const vector<int>& b)
{
	vector<int> merged_a_b(a.size()+b.size(),0); // temp vector that includes both left and right vectors
	int i = 0;
	int j = 0;
	int k = 0;
	int left_size = a.size();
	int right_size = b.size();
	while(i<left_size && j<right_size) 
	{
		if(a[i]<b[j])
		{
			merged_a_b[k]=a[i];
			i++;
		}
		else
		{
			merged_a_b[k]=b[j];
			j++;
		}
		k++;
	}
	while(i<left_size)
	{
		merged_a_b[k]=a[i];
		i++;
		k++;
	}
	while(j<right_size)
	{
		merged_a_b[k]=b[j];
		j++;
		k++;
	}
	
	return merged_a_b;

}