merge sort c 2b 2b

1#include <iostream>
2using namespace std;
3 
4
5void merge(int arr[], int l, int m, int r)
6{
7    int n1 = m - l + 1;
8    int n2 = r - m;
9 
10 
11    int L[n1], R[n2];
12 
13   
14    for (int i = 0; i < n1; i++)
15        L[i] = arr[l + i];
16    for (int j = 0; j < n2; j++)
17        R[j] = arr[m + 1 + j];
18
19 
20    int i = 0;
21 
22    
23    int j = 0;
24 
25    
26    int k = l;
27 
28    while (i < n1 && j < n2) {
29        if (L[i] <= R[j]) {
30            arr[k] = L[i];
31            i++;
32        }
33        else {
34            arr[k] = R[j];
35            j++;
36        }
37        k++;
38    }
39 
40  
41    while (i < n1) {
42        arr[k] = L[i];
43        i++;
44        k++;
45    }
46 
47   
48    while (j < n2) {
49        arr[k] = R[j];
50        j++;
51        k++;
52    }
53}
54 
55
56void mergeSort(int arr[],int l,int r){
57    if(l>=r){
58        return;
59    }
60    int m = (l+r-1)/2;
61    mergeSort(arr,l,m);
62    mergeSort(arr,m+1,r);
63    merge(arr,l,m,r);
64}
65 
66
67void printArray(int A[], int size)
68{
69    for (int i = 0; i < size; i++)
70        cout << A[i] << " ";
71}
72 
73
74int main()
75{
76    int arr[] = { 12, 11, 13, 5, 6, 7 };
77    int arr_size = sizeof(arr) / sizeof(arr[0]);
78 
79    cout << "Given array is \n";
80    printArray(arr, arr_size);
81 
82    mergeSort(arr, 0, arr_size - 1);
83 
84    cout << "\nSorted array is \n";
85    printArray(arr, arr_size);
86    return 0;
87}

1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
3
4function merge(list, start, midpoint, end) {
5    const left = list.slice(start, midpoint);
6    const right = list.slice(midpoint, end);
7    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
8        if (topLeft >= left.length) {
9            list[i] = right[topRight++];
10        } else if (topRight >= right.length) {
11            list[i] = left[topLeft++];
12        } else if (left[topLeft] < right[topRight]) {
13            list[i] = left[topLeft++];
14        } else {
15            list[i] = right[topRight++];
16        }
17    }
18}
19
20function mergesort(list, start = 0, end = undefined) {
21    if (end === undefined) {
22        end = list.length;
23    }
24    if (end - start > 1) {
25        const midpoint = ((end + start) / 2) >> 0;
26        mergesort(list, start, midpoint);
27        mergesort(list, midpoint, end);
28        merge(list, start, midpoint, end);
29    }
30    return list;
31}
32
33mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

1#include<iostream>
2using namespace std;
3void swapping(int &a, int &b) {     //swap the content of a and b
4   int temp;
5   temp = a;
6   a = b;
7   b = temp;
8}
9void display(int *array, int size) {
10   for(int i = 0; i<size; i++)
11      cout << array[i] << " ";
12   cout << endl;
13}
14void merge(int *array, int l, int m, int r) {
15   int i, j, k, nl, nr;
16   //size of left and right sub-arrays
17   nl = m-l+1; nr = r-m;
18   int larr[nl], rarr[nr];
19   //fill left and right sub-arrays
20   for(i = 0; i<nl; i++)
21      larr[i] = array[l+i];
22   for(j = 0; j<nr; j++)
23      rarr[j] = array[m+1+j];
24   i = 0; j = 0; k = l;
25   //marge temp arrays to real array
26   while(i < nl && j<nr) {
27      if(larr[i] <= rarr[j]) {
28         array[k] = larr[i];
29         i++;
30      }else{
31         array[k] = rarr[j];
32         j++;
33      }
34      k++;
35   }
36   while(i<nl) {       //extra element in left array
37      array[k] = larr[i];
38      i++; k++;
39   }
40   while(j<nr) {     //extra element in right array
41      array[k] = rarr[j];
42      j++; k++;
43   }
44}
45void mergeSort(int *array, int l, int r) {
46   int m;
47   if(l < r) {
48      int m = l+(r-l)/2;
49      // Sort first and second arrays
50      mergeSort(array, l, m);
51      mergeSort(array, m+1, r);
52      merge(array, l, m, r);
53   }
54}
55int main() {
56   int n;
57   cout << "Enter the number of elements: ";
58   cin >> n;
59   int arr[n];     //create an array with given number of elements
60   cout << "Enter elements:" << endl;
61   for(int i = 0; i<n; i++) {
62      cin >> arr[i];
63   }
64   cout << "Array before Sorting: ";
65   display(arr, n);
66   mergeSort(arr, 0, n-1);     //(n-1) for last index
67   cout << "Array after Sorting: ";
68   display(arr, n);
69}

1def mergeSort(arr): 
2    if len(arr) >1: 
3        mid = len(arr)//2 # Finding the mid of the array 
4        L = arr[:mid] # Dividing the array elements  
5        R = arr[mid:] # into 2 halves 
6  
7        mergeSort(L) # Sorting the first half 
8        mergeSort(R) # Sorting the second half 
9  
10        i = j = k = 0
11          
12        # Copy data to temp arrays L[] and R[] 
13        while i < len(L) and j < len(R): 
14            if L[i] < R[j]: 
15                arr[k] = L[i] 
16                i+= 1
17            else: 
18                arr[k] = R[j] 
19                j+= 1
20            k+= 1
21          
22        # Checking if any element was left 
23        while i < len(L): 
24            arr[k] = L[i] 
25            i+= 1
26            k+= 1
27          
28        while j < len(R): 
29            arr[k] = R[j] 
30            j+= 1
31            k+= 1
32  
33# Code to print the list 
34def printList(arr): 
35    for i in range(len(arr)):         
36        print(arr[i], end =" ") 
37    print() 
38  
39# driver code to test the above code 
40if __name__ == '__main__': 
41    arr = [12, 11, 13, 5, 6, 7]  
42    print ("Given array is", end ="\n")  
43    printList(arr) 
44    mergeSort(arr) 
45    print("Sorted array is: ", end ="\n") 
46    printList(arr)

1/*  
2    a[] is the array, p is starting index, that is 0, 
3    and r is the last index of array. 
4*/
5
6#include <stdio.h>
7
8// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
9
10// merge sort function
11void mergeSort(int a[], int p, int r)
12{
13    int q;
14    if(p < r)
15    {
16        q = (p + r) / 2;
17        mergeSort(a, p, q);
18        mergeSort(a, q+1, r);
19        merge(a, p, q, r);
20    }
21}
22
23// function to merge the subarrays
24void merge(int a[], int p, int q, int r)
25{
26    int b[5];   //same size of a[]
27    int i, j, k;
28    k = 0;
29    i = p;
30    j = q + 1;
31    while(i <= q && j <= r)
32    {
33        if(a[i] < a[j])
34        {
35            b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
36        }
37        else
38        {
39            b[k++] = a[j++];
40        }
41    }
42  
43    while(i <= q)
44    {
45        b[k++] = a[i++];
46    }
47  
48    while(j <= r)
49    {
50        b[k++] = a[j++];
51    }
52  
53    for(i=r; i >= p; i--)
54    {
55        a[i] = b[--k];  // copying back the sorted list to a[]
56    } 
57}
58
59// function to print the array
60void printArray(int a[], int size)
61{
62    int i;
63    for (i=0; i < size; i++)
64    {
65        printf("%d ", a[i]);
66    }
67    printf("\n");
68}
69 
70int main()
71{
72    int arr[] = {32, 45, 67, 2, 7};
73    int len = sizeof(arr)/sizeof(arr[0]);
74 
75    printf("Given array: \n");
76    printArray(arr, len);
77    
78    // calling merge sort
79    mergeSort(arr, 0, len - 1);
80 
81    printf("\nSorted array: \n");
82    printArray(arr, len);
83    return 0;
84}

1#include "tools.hpp"
2/*   >>>>>>>> (Recursive function that sorts a sequence of) <<<<<<<<<<<< 
3     >>>>>>>> (numbers in ascending order using the merge function) <<<<                                 */
4std::vector<int> sort(size_t start, size_t length, const std::vector<int>& vec)
5{
6	if(vec.size()==0 ||vec.size() == 1)
7	return vec;
8
9	vector<int> left,right; //===>  creating left and right vectors 
10
11	size_t mid_point = vec.size()/2; //===>   midle point between the left vector and the right vector 
12
13	for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);} //===>  left vector 
14	for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);} //===>  right vector 
15
16	left = sort(start,mid_point,left); //===>  sorting the left vector 
17	right = sort(mid_point,length-mid_point,right);//===>  sorting the right vector 
18	
19
20	return merge(left,right); //===>   all the function merge to merge between the left and the right
21}
22/*
23
24>>>>> (function that merges two sorted vectors of numberss) <<<<<<<<<                                    */ 
25vector<int> merge(const vector<int>& a, const vector<int>& b)
26{
27	vector<int> merged_a_b(a.size()+b.size(),0); // temp vector that includes both left and right vectors
28	int i = 0;
29	int j = 0;
30	int k = 0;
31	int left_size = a.size();
32	int right_size = b.size();
33	while(i<left_size && j<right_size) 
34	{
35		if(a[i]<b[j])
36		{
37			merged_a_b[k]=a[i];
38			i++;
39		}
40		else
41		{
42			merged_a_b[k]=b[j];
43			j++;
44		}
45		k++;
46	}
47	while(i<left_size)
48	{
49		merged_a_b[k]=a[i];
50		i++;
51		k++;
52	}
53	while(j<right_size)
54	{
55		merged_a_b[k]=b[j];
56		j++;
57		k++;
58	}
59	
60	return merged_a_b;
61
62}