要按照输入顺序对输出对象进行排序并避免O(n^2)的时间复杂度，可以使用稳定的排序算法，并且在排序过程中记录每个元素的原始索引。

以下是一个示例代码，使用归并排序实现按照输入顺序对输出对象进行排序：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        # 比较左右两个数组中元素的大小，并按照原始索引的顺序合并到结果数组中
        if left[i][1] <= right[j][1]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    
    # 将剩余的元素合并到结果数组中
    while i < len(left):
        merged.append(left[i])
        i += 1
    
    while j < len(right):
        merged.append(right[j])
        j += 1
    
    return merged

# 示例输入
input_objects = [("obj1", 3), ("obj2", 1), ("obj3", 2)]

# 在输入对象中添加原始索引
indexed_objects = [(obj[0], i, obj[1]) for i, obj in enumerate(input_objects)]

# 使用归并排序按照输入顺序对输出对象进行排序
sorted_objects = merge_sort(indexed_objects)

# 输出排序后的对象
for obj in sorted_objects:
    print(obj[0])

在上述示例代码中，我们首先将输入对象转换为带有原始索引的形式。然后，我们使用归并排序算法按照输入顺序对这些对象进行排序。在合并过程中，我们根据元素的大小比较结果和原始索引的顺序将它们合并到结果数组中。最后，我们输出排序后的对象。

这种方法的时间复杂度为O(nlogn)，其中n是输入对象的数量。由于我们使用了稳定的归并排序算法，并在排序过程中记录原始索引，因此可以保持按照输入顺序对输出对象进行排序。