merge sort c

1#include <stdio.h>
2
3void merge(int arr[], int start, int mid, int end) {
4
5  int len1 = mid - start + 1;
6  int len2 = end - mid;
7
8  int leftArr[len1], rightArr[len2];
9
10  for (int i = 0; i < len1; i++)
11    leftArr[i] = arr[start + i];
12  for (int j = 0; j < len2; j++)
13    rightArr[j] = arr[mid + 1 + j];
14
15  int i, j, k;
16  i = 0;
17  j = 0;
18  k = start;
19
20  while (i < len1 && j < len2) {
21    if (leftArr[i] <= rightArr[j]) {
22      arr[k] = leftArr[i];
23      i++;
24    } else {
25      arr[k] = rightArr[j];
26      j++;
27    }
28    k++;
29  }
30
31  while (i < len1) {
32    arr[k] = leftArr[i];
33    i++;
34    k++;
35  }
36
37  while (j < len2) {
38    arr[k] = rightArr[j];
39    j++;
40    k++;
41  }
42}
43
44void mergeSort(int arr[], int start, int end) {
45  if (start < end) {
46
47    int mid = start + (end - start) / 2;
48    mergeSort(arr, start, mid);
49    mergeSort(arr, mid + 1, end);
50    merge(arr, start, mid, end);
51  }
52}
53
54void display(int arr[], int size) {
55  for (int i = 0; i < size; i++)
56    printf("%d ", arr[i]);
57  printf("\n");
58}
59
60int main() {
61  int arr[] = {6, 5, 12, 10, 9, 1};
62  int size = sizeof(arr) / sizeof(arr[0]);
63  
64  printf("Original array\n");
65  display(arr, size);
66  
67  mergeSort(arr, 0, size - 1);
68
69  printf("Sorted array\n");
70  display(arr, size);
71}
72

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]);

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#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}