Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

Write merge sort in C++

  1. User

    Write merge sort in C++

  2. Assistant
    #include<bits/stdc++.h>
    using namespace std;
    
    void merge(vector<int> &a, int low, int mid, int high) {
        int n1 = mid - low + 1;
        int n2 = high - mid;
    
        vector<int> left(n1), right(n2);
    
        for (int i = 0; i < n1; i++)
            left[i] = a[low + i];
        for (int i = 0; i < n2; i++)
            right[i] = a[mid + 1 + i];
    
        int i = 0, j = 0, k = low;
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                a[k++] = left[i++];
            } else {
                a[k++] = right[j++];
            }
        }
    
        while (i < n1)
            a[k++] = left[i++];
    
        while (j < n2)
            a[k++] = right[j++];
    }
    
    void mergeSort(vector<int> &a, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSort(a, low, mid);
            mergeSort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
    }
    
    int main() {
        vector<int> a = {12, 11, 13, 5, 6, 7};
        int n = a.size();
        
        cout<<"Given array is: "<<endl;
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        
        mergeSort(a, 0, n - 1);
    
        cout<<"Sorted array is: "<<endl;
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    
        return 0;
    }
    

    This code begins by importing the required libraries, and then the merge function is defined. This function is responsible for merging the two sub-arrays, formed by dividing the main array, into a single sorted array. The mergeSort function is then defined, which applies the mergeSort algorithm to a given array. The main function initializes an array and calls the mergeSort function to sort the array. The given array and the sorted array are then printed to the console.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.