java - Creating own singly linked list to sort -
i'm trying create own singly linked list in java , use perform sorting. have access first node , next pointer used point next node. every node contains 2 fields x , y both integers. how add elements linked list without using built in methods , sort them using either quicksort or merge sort?
how add elements linked list without using built in methods , sort them using either quicksort or merge sort?
fast algorithms quicksort , mergesort depend on being able >>index<< array of elements being sorted; i.e. in operation sequences a[i] = a[j]. using linked list means random indexing o(n) operation. turn o(n log n) algorithm o(n^2 log n) one.
if @ java's built-in sort methods (in various versions of java), see sorting linkedlist done by:
- copying list temporary array,
- sorting array, ,
- clearing , copying array list.
this efficient approach sorting large linked list.
