Making the complexity smaller (better)

One of the most well-known divide-and-conquer algorithms is merge sort. And merge sort is actually a really good foundation for this algorithm.

The idea is that when comparing two numbers from two different 'partitions', you already have a lot of information about the remaining part of these partitions, as they're sorted in every iteration.

Let's take an example!

Consider the following partitions, which has already been sorted individually and "good pairs" have been counted.

Partition x: [1, 3, 6, 9].

Partition y: [4, 5, 7, 8].

It is important to note that the numbers from partition x is located further to the left in the original list than partition y. In particular, for every element in x, it's corresponding index i must be smaller than some index j for every element in y.

We will start of by comparing 1 and 4. Obviously 1 is smaller than 4. But since 4 is the smallest element in partition y, 1 must also be smaller than the rest of the elements in y. Consequently, we can conclude that there is 4 additional good pairs, since the index of 1 is also smaller than the index of the remaining elements of y.

The exact same thing happens with 3, and we can add 4 new good pairs to the sum.

For 6 we will conclude that there is two new good pairs. The comparison between 6 and 4 did not yield a good pair and likewise for 6 and 5.

You might now notice how these additional good pairs would be counted? Basically if the element from x is less than the element from y, add the number of elements remaining in y to the sum. Rince and repeat.

Since merge sort is an O(n log n) algorithm, and the additional work in this algorithm is constant, we can conclude that this algorithm is also an O(n log n) algorithm.

I will leave the actual programming as an exercise for you.

The current previously accepted answer by Fire Assassin doesn't really answer the question, which asks for better complexity. It's still quadratic, and about as fast as a much simpler quadratic solution. Benchmark with 2000 shuffled ints:

387.5 ms  original
108.3 ms  pythonic
104.6 ms  divide_and_conquer_quadratic
  4.1 ms  divide_and_conquer_nlogn
  4.6 ms  divide_and_conquer_nlogn_2

Code (Try it online!):

def original(nums):
    count = 0
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):    
            if i < j and nums[i] < nums[j]:
                count += 1
                j += 1
            j += 1
    return count

def pythonic(nums):
    count = 0
    for i, a in enumerate(nums, 1):
        for b in nums[i:]:
            if a < b:
                count += 1
    return count

def divide_and_conquer_quadratic(arr):
    count = 0 
    left_count = 0
    right_count = 0
    if len(arr) > 1:
        mid = len(arr) // 2
        left_side = arr[:mid]
        right_side = arr[mid:]
        left_count = divide_and_conquer_quadratic(left_side)
        right_count = divide_and_conquer_quadratic(right_side)
        for i in left_side:
            for j in right_side:
                if i < j:
                    count += 1
    return count + left_count + right_count

def divide_and_conquer_nlogn(arr):
    mid = len(arr) // 2
    if not mid:
        return 0
    left = arr[:mid]
    right = arr[mid:]
    count = divide_and_conquer_nlogn(left)
    count += divide_and_conquer_nlogn(right)
    i = 0
    for r in right:
        while i < mid and left[i] < r:
            i += 1
        count += i
    arr[:] = left + right
    arr.sort()  # linear, as Timsort takes advantage of the two sorted runs
    return count

def divide_and_conquer_nlogn_2(arr):
    mid = len(arr) // 2
    if not mid:
        return 0
    left = arr[:mid]
    right = arr[mid:]
    count = divide_and_conquer_nlogn_2(left)
    count += divide_and_conquer_nlogn_2(right)
    i = 0
    arr.clear()
    append = arr.append
    for r in right:
        while i < mid and left[i] < r:
            append(left[i])
            i += 1
        append(r)
        count += i
    arr += left[i:]
    return count

from timeit import timeit
from random import shuffle

arr = list(range(2000))
shuffle(arr)

funcs = [
    original,
    pythonic,
    divide_and_conquer_quadratic,
    divide_and_conquer_nlogn,
    divide_and_conquer_nlogn_2,
]

for func in funcs:
    print(func(arr[:]))

for _ in range(3):
    print()
    for func in funcs:
        arr2 = arr[:]
        t = timeit(lambda: func(arr2), number=1)
        print('%5.1f ms ' % (t * 1e3), func.__name__)

@niklasaa has added an explanation for the merge sort analogy, but your implementation still has an issue.

You are partitioning the array and calculating the result for either half, but

1. You haven't actually sorted either half. So when you're comparing their elements, your two pointer approach isn't correct.
2. You haven't used their results in the final computation. That's why you're getting an incorrect answer.

For point #1, you should look at merge sort, especially the merge() function. That logic is what will give you the correct pair count without having O(N^2) iteration.

For point #2, store the result for either half first:

# Sorting the first half
leftCount = goodPairs(left_side)
  
# Sorting the second half
rightCount = goodPairs(right_side)

While returning the final count, add these two results as well.

return count + leftCount + rightCount

Like @Abhinav Mathur stated, you have most of the code down, your problem is with these lines:

# Sorting the first half
goodPairs(left_side)

# Sorting the second half
goodPairs(right_side)

You want to store these in variables that should be declared before the if statement. Here's an updated version of your code:

def goodPairs(arr):
    count = 0 
    left_count = 0
    right_count = 0

    if len(arr) > 1:
        mid = len(arr) // 2
  
        left_side = arr[:mid]
  
        right_side = arr[mid:]
  
        left_count = goodPairs(left_side)
  
        right_count = goodPairs(right_side)

        for i in left_side:
            for j in right_side:
                if i < j:
                    count += 1
    return count + left_count + right_count

Recursion can be difficult at times, look into the idea of merge sort and quick sort to get better ideas on how the divide and conquer algorithms work.