Q:

Finding time and space complexity

I have been learning about sorting.
Most of sorting algorithms(merge, quick, etc) utilise arrays.
I was thinking what if I did not sort an array in place.
An algorithm I thought of is

Iterate through each element in array - O(n).
For each element, compare the element with starting and ending element of a doubly linked list.
Add the element to correct position in linked list. (Start iterating from start/end of list based on which one would be faster).
When all elements in original array are sorted, create background thread which copies them into array. Until copy is not done, return index element by iterating over list.
When copy is done, return elements through array index.

Now, what would be time complexity of this and how do I calculate it?

A:

Let's go through everything one step at a time.

Iterate through each element in array - O(n).

Yep!

For each element, compare the element with starting and ending element of a doubly linked list.
Add the element to correct position in linked list. (Start iterating from start/end of list based on which one would be faster).

Let's suppose that the doubly-linked list currently has k elements in it. Unfortunately, just by looking at the front and back element of the list, you won't be able to tell where in the list the element is likely to go. It's quite possible that your element is closer in value to the front element of the list than the back, but would actually belong just before the back element. You also don't have random access in a linked list, so in the worst case you may have to scan all k elements of the linked list trying to find the spot where this element belongs. That means that the work done is in the worst case going to be O(k). Now, each iteration of the algorithm increases k (the number of elements in the list) by one, so the work done is in the worst case 1 + 2 + 3 + ... + n = Θ(n2).

When all elements in original array are sorted, create background thread which copies them into array. Until copy is not done, return index element by iterating over list.
When copy is done, return elements through array index.

This is an interesting idea and it's hard to measure the complexity. If the background thread gets starved out or is really slow, then the cost of looking up any element will be O(n) in the worst case because you may have to scan over half the elements in the list to find the one you're looking for.
In total, your algorithm runs in time O(n2) and uses Θ(n)  memory. It's essentially a variant of insertion sort (as @Yu Hao) pointed out and, in practice, I'd expect that this would be substantially slower than just using a standard O(n log n) sorting algorithm, or even an in-place insertion sort, due to the extra memory overhead and poor locality of reference afforded by linked lists.

