Java Community | Help. Code. Learn.•8mo ago

SIMPLE RECURSIVE QUESTION

Consider this code:

public void mergeSort(int[] arrayToSort, int length) {
        if (length < 2) {
            return;
        }

        int[] left = new int[length/2];
        int[] right = new int[length - length/2];

        for (int i=0; i<length/2; i++) {
            left[i] = arrayToSort[i];
        }

        int index = 0;
        for (int i=length/2; i<length; i++) {
            right[index] = arrayToSort[i];
            index++;
        }

        mergeSort(left, length/2);
        mergeSort(right, length - length/2);
        merge(left,right,arrayToSort);
        for (int i=0; i<arrayToSort.length; i++) {
            System.out.println(arrayToSort[i]);
        }
    }

    public void merge(int[] leftArray, int[] rightArray, int[] originalArray) {
        int l = 0;
        int r = 0;
        int o = 0;

        while (l < leftArray.length && r < rightArray.length) {
            if (leftArray[l] < rightArray[r]) {
                originalArray[o] = leftArray[l];
                l++;
                o++;
            } else {
                originalArray[o] = rightArray[r];
                r++;
                o++;
            }
        }

        while (l < leftArray.length) {
            originalArray[o] = leftArray[l];
            l++;
            o++;
        }

        while (r < rightArray.length) {
            originalArray[o] = rightArray[r];
            r++;
            o++;
        }
    }

public void mergeSort(int[] arrayToSort, int length) {
        if (length < 2) {
            return;
        }

        int[] left = new int[length/2];
        int[] right = new int[length - length/2];

        for (int i=0; i<length/2; i++) {
            left[i] = arrayToSort[i];
        }

        int index = 0;
        for (int i=length/2; i<length; i++) {
            right[index] = arrayToSort[i];
            index++;
        }

        mergeSort(left, length/2);
        mergeSort(right, length - length/2);
        merge(left,right,arrayToSort);
        for (int i=0; i<arrayToSort.length; i++) {
            System.out.println(arrayToSort[i]);
        }
    }

    public void merge(int[] leftArray, int[] rightArray, int[] originalArray) {
        int l = 0;
        int r = 0;
        int o = 0;

        while (l < leftArray.length && r < rightArray.length) {
            if (leftArray[l] < rightArray[r]) {
                originalArray[o] = leftArray[l];
                l++;
                o++;
            } else {
                originalArray[o] = rightArray[r];
                r++;
                o++;
            }
        }

        while (l < leftArray.length) {
            originalArray[o] = leftArray[l];
            l++;
            o++;
        }

        while (r < rightArray.length) {
            originalArray[o] = rightArray[r];
            r++;
            o++;
        }
    }

assume we call mergeSort with array: 8, 2, 5, 3, 4, 7, 6, 1 at some point left array will be 8 and right array will be 2 in which they will just return and do nothing, then the left array is 8,2 and the right array is 5,3 5 and 3 and they return so we have left array 8,2 and right array 5,3 how the fuck do these get sorted im losing my mind, because my m,erge algorithm assumes they are both already sorted,

16 Replies

JavaBot•8mo ago

⌛ This post has been reserved for your question.

Hey @userexit! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

JavaBot•8mo ago

Please format your code to make it more readable. For java, it should look like this:

```java
public void foo() {
 
}
```

```java
public void foo() {
 
}
```

userexitOP•8mo ago

!help

Unknown User•8mo ago

Message Not Public

userexitOP•8mo ago

yea so do u get what im not visualizing at some point ill have 8 and 2 and they are both length < 2 so i will return then i have left array 8,2 and right array 5,3 if i execute my merge function with that, i get 5,3,8,2 which should not be sorted but it is sorted when i run the algorithmxd wait i think i get it

userexitOP•8mo ago

userexitOP•8mo ago

this is what actually happens

Unknown User•8mo ago

Message Not Public

userexitOP•8mo ago

not really then the left array is 8 and the right array is 2, and they both get sorted in the merge helper function this is the correction

Unknown User•8mo ago

Message Not Public

userexitOP•8mo ago

this is the right image I will have 8,2, length is equal to 2 so ok, then left array is 8, then right array is 2, i call mergeSort with 8 it returns, I call mergeSort with 2 it returns, then I call merge with array: 8 and with array: 2, and that sorts them thats what I was failing to comprehend

Unknown User•8mo ago

Message Not Public

userexitOP•8mo ago

the issue here was my visualization of the recursive function its all the left first then goes back up then starts constructing the rights

Unknown User•8mo ago

Message Not Public

JavaBot•8mo ago

💤 Post marked as dormant

This post has been inactive for over 300 minutes, thus, it has been archived. If your question was not answered yet, feel free to re-open this post or create a new one. In case your post is not getting any attention, you can try to use /help ping. Warning: abusing this will result in moderative actions taken against you.

Gaming

Programming

SIMPLE RECURSIVE QUESTION