Sort 3, 1, 4, 5, 9, 2, 6 using mergesort.

Sure, here are the steps to sort the given numbers using mergesort:

1. Divide the array into two halves: {3, 1, 4} and {5, 9, 2, 6}.

2. Recursively sort each half using mergesort:

a. Sort the left half {3, 1, 4} by dividing it into {3} and {1, 4}, then merging them to get {1, 3, 4}.

b. Sort the right half {5, 9, 2, 6} by dividing it into {5, 9} and {2, 6}, then merging them to get {2, 5, 6, 9}.

3. Merge the two sorted halves to get the final sorted array: {1, 2, 3, 4, 5, 6, 9}.

Therefore, the sorted array using mergesort is {1, 2, 3, 4, 5, 6, 9}.

相关问题

Write a code to sort the following array in ascending order and show the sorted numbers using the following algorithm methods. (A)QuickSort algorithm (B) MergeSort algorithm arr = [12, 11, 13, 5, 6, 7]

A) QuickSort algorithm:

def quickSort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quickSort(left) + [pivot] + quickSort(right)

arr = [12, 11, 13, 5, 6, 7]
sorted_arr = quickSort(arr)
print(sorted_arr)

Output: `[5, 6, 7, 11, 12, 13]`

B) MergeSort algorithm:

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

arr = [12, 11, 13, 5, 6, 7]
sorted_arr = mergeSort(arr)
print(sorted_arr)

Output: `[5, 6, 7, 11, 12, 13]`

C++mergesort array

Here is an implementation of mergesort algorithm in C to sort an array:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];
    for(i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for(j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    k = left;

    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while(i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while(j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergesort(int arr[], int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;

        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

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

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergesort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

The `merge` function takes the left, middle, and right indices of the array as input and merges the two subarrays left to mid and mid+1 to right into a single sorted array. The `mergesort` function recursively divides the input array into two halves, sorts them, and then merges them using the `merge` function.

The `printArray` function is used to print the elements of an array.

In the main function, we define an array of integers, print the array before sorting, call the mergesort function to sort the array, and print the sorted array.