Sun Jun 08, 2008 5:48 pm
This is off the top of my head, so someone can feel free to correct me:
Let us also assume that the sort used will require random access to the elements in the array (i.e. it will require access to any element at any time). For an array based structure, you'll be able to achieve that randomness using the element index, and that's an O(1) operation. Since we need to access each element at least once (O(n)), and we have log n comparisons to perform (average case for merge sort), we get O(n log n) complexity.
However, in a linked list, accessing a random element is an O(n) operation (you have to start at one end, and work your way to the other, by definition of a LL). Thus accessing each element has a complexity of O(n^2). Thus the final runtime complexity of O (n^2 log n).
Since dumping the linked list to an array is O(n), the dump and sort method would be O (n) + O (n log n), which is O (n log n) in the end.
Not familiar with the java API, and if it gives you a LL in the end. Assuming it does, the complexity does go up a little, but a couple small tricks will still keep it down to O(n log n).
Intel i7 4790k @ stock, Asus Z97-PRO(Wi-Fi ac), 2x8GB Crucial DDR3 1600MHz, EVGA GTX 760
Samsung 950 Pro 512GB + 2TB Western Digital Black
Dell 2408WFP and Dell 2407WFP-HC for dual-24" goodness
Windows 10 64-bit