MergeSort without merge function,, How does this algorithm merges the lists

def mergeSort(A):
    if len(A) < 2:
        return A

    mid = int(len(A)/2)
    left = mergeSort(A[:mid])
    right = mergeSort(A[mid:])

    r,l = 0,0
    B = []

    while len(B) < len(A):
        if r >= len(right) or (l < mid and left[l] < right[r]):
            B.append(left[l])
            l += 1
        elif r < len(right):
            B.append(right[r])
            r += 1

    return B

print(mergeSort([4,3,6,9,8,5,1]))

My doubt in the above program is how the lists are merged without a separate merge function?

After the recursive function calls in the end I think left and right lists contain only one element each... they are sorted and inserted in to list B using a while loop... what about other elements.. because here while loop is executed only once and how the list A is again split and merged...I got this program in internet and it works perfectly fine.

I think your problem is that you don't understand how recursion works. The while loop isn't only executed once, it's executed once per (non-trivial) recursive call.

It's worth tracing through the operation. Whether you do it on paper, in the debugger, using a graphical visualizer like this one, or just by using a bunch of print calls, it's the only way you're really going to understand exactly what's going on.

I think the graphical visualizer will be easier to follow, but learning how to do it on paper is worthwhile, so let's do that. We only need to step through one of the non-trivial merges, because after that they all look the same.

• Sort [4,3,6,9,8,5,1]
• Sort [4,3,6]
• Sort [4] * Because [4] has length 0 or 1, trivially sort it by just returning it as-is.
• Sort [3, 6] * Sort [3]
  • Because [3] has length 0 or 1, trivially sort it by just returning it as-is. * Sort [6]
  • Because [6] has length 0 or 1, trivially sort it by just returning it as-is. * Merge the sorted [3] and [6] halves (if you're using the graphical visualizer, this happens at step 31; if using the debugger, put a breakpoint at line 12 and this will be the first time the breakpoint is hit):
  • Start with l, r, B = 0, 0, []
  • Since len([]) < len([3, 6]), we're not done.
  • Since the first if condition is true, append from left and increment l, so l, r, B = 1, 0, [3].
  • Since len([3]) < len([3, 6]), we're not done.
  • Since the first if condition is false and the second is true, append from right and increment r, so l, r, B = 1, 1, [3, 6].
  • Since len([3, 6]) == len([3, 6]), we're done.
• Merge the sorted [4] and [3, 6] halves the same way as above.
• Sort [9, 8, 5, 1].
• This goes the same as the above, and will include trivially returning 4 single-element lists, plus using the while loop to merge [9] and [8], and [5] and [1], and [8, 9] and [1, 5] along the way; you can step through the details yourself if you don't understand how that works.
• Merge the sorted [3, 4, 6] and [1, 5, 8, 9] halves the same way as above.

As you can see, the while loop is actually executed six times, not just once.