What is the time complexity of this problem?

The following pseudo-code represents an algorithm that takes as input an array of elements that can contain either positive integers or strings. In other words, the input could look like this [42, 'a', 1, 'hello', 3] .

The algorithm outputs an array with the following properties: elements in the output alternate between being a string and being an integer, and each element is less than or equal to the previous element of the same type (except for the elements at position 1 and 2, which are the largest of their respective types). In computer science, it is possible to sort strings ('b' > 'a', for example). This output will contain more elements than the input if the input does not have the same number of integers and strings.

What is the runtime of this algorithm?

For this example, assume that the sorting algorithm Reverse_Cheating_Sort(A) is a constant $O(1)$ operation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Crazy_Sort(A):
    strings = []
    integers = []
    num_strings = 0
    num_integers = 0
    for i = 1 to i = A.length:
        if type(A[i]) == 'string':
            num_strings = num_strings + 1
            strings.push(A[i])
        else:
            num_integers = num_integers + 1
            integers.push(A[i])
    if num_strings > num_integers:
        for i = 1 to i = num_strings - num_integers:
            integers.push(1)
    else if num_integers > num_strings:
        for i = 1 to i = num_integers - num_strings:
            strings.push('a')
    result = []
    strings = Reverse_Cheating_Sort(strings)
    integers = Reverse_Cheating_Sort(integers)
    for i = 1 to i = strings.length:
        result.push(strings[0])
        result.push(integers[0])
    return result