Linked List merge sort implementation attempt with Python runs into an infinite loop

Context

I was implementing a LinkedList sort solution with python (over on leetcode.com).
The solution is a bottom up merge sort approach (divide and conquer).
The code below is incomplete, it’s missing the implementation of the merge() method, which will take a list of a given size and merge it, given that the two halves of the list were already sorted i.e. take a half and inset it somewhere in the other half.

I ran into my issue while testing the other parts of the implementation.

sortList() and merge_list_of_size()
The idea is that sortList() will start by considering all the sublists of size 2, and sorting them by calling merge_list_of_size() with list_size = 2.
The sortList() will continue by doubling the list_size, list_size = 4, and again use merge_list_of_size() to sort all lists of that size.
The list size will increase again and again until the list_size is too large to continue.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        N = 1
        while N < 100:
            N *= 2
            print(N)
            has_next_merge = self.merge_list_of_size(head, N)
            if not has_next_merge:
                print('has_next_merge', has_next_merge)
                break
        return head

    def merge_list_of_size(self, head, list_size):
        while head:
            print('--', head)
            next_merge = self.merge(head, list_size)
            if not next_merge:
                return False

            i = list_size
            while head and i > 0:
                head = head.next
                i -= 1
        return True

    def merge(self, head, list_size):
        mid_i = list_size // 2
        print(mid_i)
        mid = head
        while mid.next and mid_i > 1:
            mid = mid.next
            mid_i -= 1
        print('----', mid)
        if mid.next is None:
            return False
        else:
            # merge
            print('merging')
            return True

The infinite loop issue

When running the code above, with an input of this linked list: [4,2,1,3].
Notice the while in sortList().
The Loop breaks either if:

1. merge_list_of_size() returns a False
2. N is >= 100

This is the log output:

2
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
1
---- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
merging
-- ListNode{val: 1, next: ListNode{val: 3, next: None}}
1
---- ListNode{val: 1, next: ListNode{val: 3, next: None}}
merging
4
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
2
---- ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}
merging
8
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
4
---- ListNode{val: 3, next: None}
has_next_merge False

1. There is no infinite loop
2. The program exits as expected when the merge_list_of_size() returns a False on N = 8.

If I now change the while from while N < 100: to while True:, for some reason unknown to me, the loop is not possible to break. And this is the log output I get:

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
.
.
.

Not sure what I’m missing here. I would appreciate any hints. Thanks.
Here’s the link to the leetcode problem.

You need to sign in to view this answers