Geek Answers Handbook

Combine sorting, where are the sublists stored?

I have included the code that I am using.

I understand that the beginning of the code continues to separate the sublist until you have values. Unit values ​​are stored in the lefthalf and righthalf variables and then combined in sorted order.

How does code combine two lists of two elements? As I can see, these sublists are stored in separate local variables called alist, how are they combined?

def mergeSort(alist):

    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0

        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1


        while i < len(lefthalf): 
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1


        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
+4
source share
2 answers

while lefthalf, righthalf, . (lefthalf, righthalf )

while i < len(lefthalf) and j < len(righthalf):
    if lefthalf[i] < righthalf[j]:
        # Pick the smallest item from `leftHalf` if has a smaller item
        alist[k]=lefthalf[i]
        i=i+1
    else:
        # Pick smallest item from `rightHalf`
        alist[k]=righthalf[j]
        j=j+1
    k = k + 1
    # `k` keeps track position of `alist`
    # (where to put the smallest item)
    # Need to increase the `k` for the next item

, while alist. ; while.

: alist[k] = ... alist .

+3

, inplace mergeSort, . ( , ). , :

def mergeSort(alist):

    if len(alist)>1:  # empty lists and lists of one element are sorted already
        mid = len(alist)//2  # find the halfway point
        lefthalf = alist[:mid]  # make a copy of the first half of the list
        righthalf = alist[mid:] # make a copy of the second half of the list 

        mergeSort(lefthalf)
        mergeSort(righthalf)

        # Each half is now sorted

        # Now we're going to copy elements from lefthalf and righthalf
        # back into alist. We do this by keeping three index variables:
        # where we are in lefthalf (i), where we are in righthalf (j)
        # and where we are going to put stuff in alist (k)

        i=0
        j=0
        k=0

        while i < len(lefthalf) and j < len(righthalf):
            # that is, "while we still have stuff left in both halves":

            if lefthalf[i] < righthalf[j]:
                # The thing we're looking at in lefthalf is smaller
                # than what we have in righthalf. Copy the thing in
                # lefthalf over to alist, and increment i
                alist[k]=lefthalf[i]
                i=i+1
            else:
                # same story, but on the right half
                alist[k]=righthalf[j]
                j=j+1
            k=k+1


        # If we ran out of stuff in righthalf first, finish up copying
        # over all the rest of the stuff in lefthalf
        while i < len(lefthalf): 
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1


        # If we ran out of stuff in lefthalf first, finish up copying
        # over all the rest of the stuff in righthalf
        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

        # Note that only one of those while loops will actually do anything -
        # the other while loop will have its condition false the first time
+3

More articles:


All Articles