Search code examples
javaarraysalgorithmloopsdivide-and-conquer

What are this java while loops doing in merge sort?


Step one and step two (step three) seem like repeatedly running to me. Why is it programmed like this?

    int i = 0, j = 0; 
    int k = l; 
    while (i < n1 && j < n2) {     ----step one
        if (L[i] <= R[j]){ 
            arr[k] = L[i]; 
            i++; 
        } 
        else{ 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1){             ---step two
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    while (j < n2){         ----step three
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
}

Solution

  • "Step one" does the work of merging from two source arrays into the destination. When L or R is exhausted there may still be unmerged elements remaining in the other source array. "Step two" exists to copy any remaining elements from L to the destination. "Step three" serves the same purpose for R.