For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:def algo_X(A):    i = 0    j = len(A)-1    while i < j:        if A[i] != A[j]:            k = i + 1            while k < j:                if A[i] == A[k]:                    A[k], A[j] = A[j], A[k]                    break                elif A[j] == A[k]:                    A[k], A[i] = A[i], A[k]                    break                else:                    k += 1            if k == j:                return False        i += 1        j -= 1    return TrueThis algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False.For example, this list ['a', 'a', 'b', '2', 'b', 'b', 2] can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right: ['a', 'b', '2', 'b', '2', 'b', a].Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and (n) in the best case.The exercise specifically states that I don't have necessarily to change the list (like in algo_X), but just to return True or False specifying respectively if the list can be made a palindrome or not. We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't know exactly the time complexity of those functions. I will edit my questionTo make a better algorithm for the worst case, I thought I could use merge sort, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.This is my merge function for my merge sort function:def merge(A, B):    ls = []    a, b = 0, 0    while a < len(A) and b < len(B):        if A[a] <= B[b]:            ls.append(A[a])            a += 1        else:            ls.append(B[b])            b += 1    while a < len(A):        ls.append(A[a])        a += 1    while b < len(B):        ls.append(B[b])        b += 1    return lsThis is my merge sort function:def merge_sort(A):    if len(A) < 2:  # basic condition        return A    L = merge_sort(A[0:len(A)//2])    R = merge_sort(A[len(A)//2:])    return merge(L, R)Finally, here's my alternative, which returns True, if the list can be made a palindrome, False otherwise:def better_algo_x(A):    if len(A) < 2:        return True    sorted_A = merge_sort(A)    odd_groups = 0    current = sorted_A[0]    c = 1  # Used to count the number of characters that are equal between them    for i in range(1, len(sorted_A)):        if current == sorted_A[i]:            c += 1        else:            if c % 2 == 1:                odd_groups += 1            if odd_groups > 1:                return False            current = sorted_A[i]            c = 1    # for the last group of characters    if c % 2 == 1:        odd_groups += 1    if odd_groups > 1:        return False    return TrueI have a few questions:Are my functions correct?  Is my analysis of the time complexity of the algorithm algo_X correct?Does my better_algo_x do what it is supposed to do? Does it do it in n*log(n) in the worst case?Can I still improve it? How?Do you know (other) better alternatives for algo_X?Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.
More efficient alternative that checks if a list can be made a palindrome
algorithms;algorithm analysis;python 3.x