java can you please handle it in a sort of beginner level . thanks a lot Based o

Question

java

can you please handle it in a sort of beginner level . thanks a lot

Based on the recursive (2-way) mergesort given below, implement a 3-way recursive mergesort algorithm. In the 3-way mergesort algorithm, the part of the array delimited by low and high will need to be divided into three subarrays and recursive calls made on each of them. Then the three subarrays will need to be merged into one sorted one. Also analyse the time complexity of the 3-way mergesort algorithm and compare it with that of (2-way) mergesort. public static void MergeSort(int[] a, int low, int high)//low and high delimit the part of the array which//is to be sorted, if there is only one element//the array is already sorted. { if (low

Explanation / Answer

Implement mergesort in arrays with a 3-way division and also print the 3 sorted partitions of the array. For example if I have as an input the following array [7 4 6 2 0 1 3 9] the output would be firstly the 3 partitions sorted: [7 4 6] [2 0] [1 3 9] and then the final array sorted [0 1 2 3 4 6 7 9].

public static void mergesort(int[] data)
{
    int data = data.length - 1;
    int length1;
    int length2;
    int length3;

    if (data % 3 == 0) {
        length1 = data / 3;
        length2 = data / 3;
        length3 = data / 3;
    } else if (data % 3 == 1) {
        length1 = (data / 3) + 1;
        length2 = data / 3;
        length3 = data / 3;
    } else { //if (data % 3 == 2)
        length1 = (data / 3) + 1;
        length2 = data / 3;
        length3 = (data / 3) + 1;
    }

    Arrays.sort(data, 0, length1 - 1);
    Arrays.sort(data, length1, length1 + length2 - 1);
    Arrays.sort(data, length1 + length2, length1 + length2 + length3 - 1);

    merge(data, 0, length1, length1 + length2);
    merge(data, 0, length1 + length2, length1 + length2 + length3);
}

private static void merge(int[] data, int first, int n1, int n2) {
    int[] temp = new int[n1 + n2];
    int ele = 0;
    int ele1 = 0;
    int ele2 = 0;
    int i;

    while ((ele1 < n1) && (ele2 < n2)) {
        if (data[first + ele1] < data[first + n1 + ele2]) {
            temp[ele++] = data[first + (ele1++)];
        } else {
            temp[ele++] = data[first + n1 + (ele2++)];
        }
    }

    while (ele1 < n1) {
        temp[ele++] = data[first + (ele1++)];
    }
    while (ele2 < n2) {
        temp[ele++] = data[first + n1 + (ele2++)];
    }

    for (i = 0; i < n1 + n2; i++) {
        data[first + i] = temp[i];
    }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.