Gice

Technology and General Blog

A record or array whose indexing (counting) commences from zero can be halved. The problem is, when the full selection of things in the list is odd, what is the left fifty percent and what is the right half. When the whole amount of elements is even, there is no trouble. If the length of the checklist is 8, say, then the left 50 % has the initially 4 factors, and the appropriate half has the up coming 4 things. If the length of the listing is 5, say, which is odd, then by convention, the left 50 percent has the very first 3 factors, and the ideal 50 percent has the following 2 features.

If the length of the list is 8, then the index for the mid (center) aspect is viewed as to be 3, which is, the 4th component – index counting starts from . So, when the length of the listing is even, the index for the mid component is length / 2 – 1.

If the duration of the record is 5, then the index for the mid factor is viewed as to be 2, which is the 3rd component. So, when the duration of the checklist is odd, the index for the mid aspect is duration / 2 – 1/2.

It is not complicated to attain the mid-index of a list with Java! – Just use integer arithmetic. The expression for the mid index is:

So, if the duration is 8, the optimum index, which is 7, is divided by 2 to give 3 and a 1/2. Integer arithmetic discards the half, leaving you with 3, which is, length / 2 – 1.

If the size is 5, the greatest index, which is 4, is divided by 2 to give 2, which is, duration / 2 – 1/2.

Merge Sort is a sorting algorithm. In this tutorial, the sorting will end result in a closing listing, from least to maximum worth. Merge Form makes use of the divide and conquer paradigm. The relaxation of this tutorial describes that, as it applies to Java.

Short article Material

Divide and Conquer for Merge Form

Divide suggests to divide the unsorted record into two halves, as explained above. Then divide each of the halves into two a lot more halves. Preserve dividing the resulting halves right until there are N lists of just one aspect every single, in which N is the length of the authentic record.

Conquer suggests start off pairing consecutive lists into a person listing though sorting the ensuing checklist. The pairing proceeds until eventually a remaining sorted record of lengths that is equal to the initial length is attained.

Take into consideration the unsorted checklist of alphabetic letters:

M  K  Q  C  E  T  G

The length of this record is 7. The next diagram illustrates how merge-sorting of this record is carried out in theory:

From the diagram, the division to one values can take 3 actions. The conquer, which is merging and sorting, requires one more 3 ways to have the sorted remaining checklist.

Should a programmer publish 6 code segments to obtain this? – No. The programmer requires to have a recursion scheme utilizing a non permanent record.

By the way, see that G appears to be fairly odd in its positioning for division of the initially suitable 50 percent. This is for the reason that the size of the record is an odd range, 7. If the duration ended up an even range, say 6, Q would have appeared as odd in a similar way for the division of the to start with still left fifty percent.

The relaxation of this posting describes “Merge Type in Java”, utilizing the unsorted checklist:

M  K  Q  C  E  T  G

The Principal Recursion Method

There are three strategies in this system. The procedures are, the divide() approach, the conquer() approach, and the main() strategy. The divide() method is the principal technique. It continuously calls alone for the remaining and correct halves and calls the conquer() technique at the close of its body. The code for the principal system is:

void divide(char arr[], int beg, int conclusion)  
        int mid  
        if (beg < end)  
            mid = (beg + end)/2  
            divide(arr, beg, mid)  
            divide(arr, mid+1, end)  
            conquer(arr, beg, mid, end)  
         
   

At the start, it takes the array given, the beginning (beg) array index, which is 0, and the ending array index, which is 6. The method will not execute if it does not have at least two elements. The check is done by the if-condition, “if (beg < end)”. The first divide() recall calls the left half of the list, and the second divide() recall calls the right to half of the list.

So, for the first execution or pass, of the divide() method, the if-condition is satisfied (more than one element). The mid index is 3 = (0 + 6) / 2 (integer arithmetic). The three method calls and their order with their arguments become:

divide(arr, 0, 3)  
divide(arr, 4, 6)
conquer(arr, 0, 3, 6)

There are three calls here. The first of these calls, calls the divide() method again for the left half of the list. The second two methods are noted and reserved in their order, to be executed later. The second divide() call would call the divide() method for the right half of the list. The conquer method would execute the two first halves together.

Before the second pass of the divide() method, the list should be considered divided into two as follows:

M  K  Q  C        E  T  G

In the second pass of the divide() method, the left half of the list is attended to. The call for the second pass is:

This time, the mid index is, 1 = (0 + 3) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 0, 1)
divide(arr, 2, 3)  
conquer(arr, 0, 1, 3)

Note that the new end index is 3, which is the end of the first left half. The first of these calls, calls the divide() method again for the left half of the first left half of the list. The second two methods are noted and reserved in their order, to be executed later, with their new arguments. The second divide() call would call the divide() method for the right half of the first left half of the list. The conquer() method would execute the two new halves.

Before the third pass of the divide() method, the list should be considered divided as follows:

M  K        Q  C        E  T  G

The third pass of the divide method is the call:

In this third pass of the divide() method, the left half of the new sub-list in question is attended to. This time, the mid index is, 0 = (0 + 1) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 0, 0)  
divide(arr, 1, 1)
conquer(arr, 0, 0, 1)

Note that the new end index is 1, which is the end of the new left half. The first of these calls is,

It fails because of the if-condition, “if (beg < end)” – beg, and end are the same, meaning there is only one element. The second divide() method,

Also fails for a similar reason. At this point, the list should be considered divided as,

M        K        Q  C        E  T  G

The third call is:

The conquer call for the two sub-lists is M and K, each consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be K M. The entire list would become:

K  M        Q  C        E  T  G

Remember that there are methods, which were noted and reserved. They would be called in reverse order, now with,

This is the fourth pass of the divide() method. It is to handle the sub-list, Q C, whose beginning index is 2 and ending index is 3. The mid index is now 2 = (2 + 3) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 2, 2)  
divide(arr, 3, 3)  
conquer(arr, 2, 2, 3)

The fifth pass of the divide() method is the call,

Note that the beginning and ending index are the same, which means there is only one element. This call fails, because of the if-condition, “if (beg < end)”. The second divide() call,

Also fails for the same reason. At this point, the list should be considered divided as,

K  M        Q        C        E  T  G

The third call in the method pass is:

The conquer call for the two sub-lists is Q and C, each consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C Q. The entire list would become:

K  M        C  Q        E  T  G

Remember that there are still methods, which were noted and reserved. They would continue to be called in reverse order now with,

This is the sixth pass of the divide() method. It is to handle the sub-list, E T G, whose beginning index is 4 and ending index is 6. The mid index is now 5 = (4 + 6) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 4, 5)  
divide(arr, 5, 6)  
conquer(arr, 4, 5, 6)

The seventh pass of the divide() method is the call,

The second two calls are noted and reserved. Note that the new end index is 5, which is the end of the new left half. The mid index is now 4 = (4 + 5) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 4, 4)  
divide(arr, 5, 5)  
conquer(arr, 4, 4, 5)

The eighth pass is:

Note that the beginning and ending index are the same, which means there is only one element. This call fails, because of the if-condition, “if (beg < end)”. The second divide() method call is,

Which also fails for the same reason. At this point, the list should be considered divided as,

K  M        C  Q        E        T  G

The third call is:

It is the conquer call for the two sub-lists: E and T : the first sub-list consisting of one element, and the second sub-list consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be E G . The entire list would become:

K  M        Q  C        E  T  G

Though the E T sequence remains the same, notice that sorting has been taking place, though the final sort is still to come.

Remember that there are still methods that were noted and reserved. They are called in reverse order. They will now be called beginning with,

Note that the new end index is 6, which is the end of the new right half. The mid index is now 5 = (5 + 6) / 2 (integer arithmetic). The method calls, their order and arguments become,

divide(arr, 5, 5)  
divide(arr, 6, 6)  
conquer(arr, 5, 5, 6)

The first two calls fail because they are addressing single element sub-lists. At this point, the entire list is:

K  M        Q  C        E  T        G

The next call is:

It is the conquer call for the two sub-lists: T and G : the first sub-list consisting of one element, and the second sub-list consisting of one element. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be G T . The entire list would become:

K  M        Q  C        E  G  T

Remember that there are still methods that were noted and reserved. They are called in reverse order. The next one to be called is,

It is the conquer call for the two sub-lists: K M and Q C: the first sub-list consisting of two elements, and the second sub-list consisting of two elements. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C K M Q. The entire list would become:

C  K  M  Q        E  G  T

Another conquer() method that was noted and reserved is:

It is the conquer call for the two sub-lists: E G and T. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be E G T. The entire list would become:

C  K  M  Q        E  G  T

The last conquer() call noted and reserved is:

It is the conquer call for the two sub-lists: C K M Q and E G T: the first sub-list consisting of four elements, and the second sub-list consisting of three elements. The conquer() method merges and sorts two sub-lists. The resulting sub-list would be C E G K M Q T, which is the entire sub-list, that is:

C  E  G  K  M  Q  T

And that ends the merging and sorting.

The conquer() Method

The conquer method merges and sorts two sub-lists. A sub-list consists of at least one value. The conquer method takes as argument, the original array, the beginning index of the first sub-list, the mid index of the two consecutive sub-lists seen together, and the end index of the second sub-list. The conquer method has a temporary array, whose length is that of the original array. The code for the conquer method is:

void conquer(char arr[], int beg, int mid, int end)  
    int i=beg, j=mid+1, k = beg, index = beg  
    char temp[] = new char[7]  
    while(i<=mid && j<=end)  
        if(arr[i]<arr[j])  
            temp[index] = arr[i]  
            i = i+1  
         
        else  
            temp[index] = arr[j]  
            j = j+1  
         
        index++  
     

    if(i>mid)  
        though(j<=end)  
            temp[index] = arr[j]  
            index++  
            j++  
         
     
    else  
        while(i<=mid)  
            temp[index] = arr[i]  
            index++
            i++  
         
     

    k = beg  
    while(k<index)
        arr[k]=temp[k]  
        k++  
     

The main method is:

public static void main(String[] args)    
        char arr[] = ‘M’, ‘K’, ‘Q’, ‘C’, ‘E’, ‘T’, ‘G’
        TheClass mergeSort = new TheClass()
        mergeSort.divide(arr,0,6)  
        System.out.println(“The Sorted Elements:”)  
        for(int i=0i<7i++)
            System.out.print(arr[i])  System.out.print(‘ ‘)
       
        System.out.println()  
   

The divide() method, the conquer() method, and the main() method should be combined into one class. The output is:

As expected.

Temporary Array for the conquer() Method

As the sub-list pairs are sorted, the result is held in the temporary array, temp[]. The arrangement of values in the temporary array ultimately replaces the content of the original array. The following shows the arrangement in the original array and that of the temporary array for the different calls of the conquer() method:

conquer(arr, 0, 0, 1)
arr[7]:  M  K  Q  C  E  T  G
temp[7]: K  M          

    conquer(arr, 2, 2, 3)  
arr[7]:  K  M  Q  C  E  T  G
temp[7]: K  M  C  Q      

    conquer(arr, 4, 4, 5)
arr[7]:  K  M  C  Q  E  T  G
temp[7]: K  M  C  Q  E  T  

    conquer(arr, 5, 5, 6)
arr[7]:  K  M  C  Q  E  T  G
temp[7]: K  M  C  Q  E  G  T

    conquer(arr, 0, 1, 3)
arr[7]:  K  M  C  Q  E  G  T
temp[7]: C  K  M  Q  E  G  T

    conquer(arr, 4, 5, 6)
arr[7]:  C  K  M  Q  E  G  T
temp[7]: C  K  M  Q  E  G  T

    conquer(arr, 0, 3, 6)
arr[7]:  C  K  M  Q  E  G  T
temp[7]: C  E  G  K  M  Q  T

Conclusion

Merge Sort is a sorting scheme that uses the divide and conquer paradigm. It divides a list of elements into single elements and then starts bringing consecutive pairs of sub-lists together, sorted, beginning from the single element sub-lists. The divide and conquer procedures are together done recursively. This tutorial has explained how it is done in Java.

Chrys

Leave a Reply

Your email address will not be published. Required fields are marked *