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}
1// Merge two subarrays L and M into arr
2void merge(int arr[], int p, int q, int r) {
3
4 // Create L ← A[p..q] and M ← A[q+1..r]
5 int n1 = q - p + 1;
6 int n2 = r - q;
7
8 int L[n1], M[n2];
9
10 for (int i = 0; i < n1; i++)
11 L[i] = arr[p + i];
12 for (int j = 0; j < n2; j++)
13 M[j] = arr[q + 1 + j];
14
15 // Maintain current index of sub-arrays and main array
16 int i, j, k;
17 i = 0;
18 j = 0;
19 k = p;
20
21 // Until we reach either end of either L or M, pick larger among
22 // elements L and M and place them in the correct position at A[p..r]
23 while (i < n1 && j < n2) {
24 if (L[i] <= M[j]) {
25 arr[k] = L[i];
26 i++;
27 } else {
28 arr[k] = M[j];
29 j++;
30 }
31 k++;
32 }
33
34 // When we run out of elements in either L or M,
35 // pick up the remaining elements and put in A[p..r]
36 while (i < n1) {
37 arr[k] = L[i];
38 i++;
39 k++;
40 }
41
42 while (j < n2) {
43 arr[k] = M[j];
44 j++;
45 k++;
46 }
47}
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}