有关排序的大多数问题都涉及对现有未排序数组进行排序。按排序顺序构造一个新数组是等效问题还是不同问题？这是一个可以澄清问题的示例：
我正在生成N随机数，并希望在生成它们时将它们插入到新数组中，并且希望对最终数组进行排序。
我的直觉告诉我，将每个元素放在生成的正确位置会是最快的。这是通过执行二分搜索来找到数组中插入新元素的正确点来完成的。然而，这是一种插入排序，众所周知，它在大型列表上的效率低于其他排序算法。
快速排序通常被认为是最有效的“通用”排序算法，其中对数组的输入一无所知，并且它比大型列表上的插入排序更有效。因此，是否最好简单地将随机数以未排序的顺序放入数组中，然后在最后使用快速排序对它们进行排序？
还有其他我没有想到的算法吗？
我是算法的新手,所以请原谅我,如果这听起来很基本或愚蠢.
我想知道这一点:不是将数据添加到某种列表中然后在列表上执行排序,而是有一种方法(数据结构+算法)可以让我在添加数据时对数据进行排序,或者放入换句话说,将数据插入适当的位置？
例如:如果我想在{1,5,6}添加'3',而不是在开头或结尾添加它然后对列表进行排序,我希望'3'直接在'1'之后".
谢谢