Why isnt this merge sort on linked list working properly?

Question

(disclaimer: for school, so cant import other Java utilities)

So I have to merge sort on a linked list, and I have almost all of it down. Here it is:

class musicNode {
String track;  // The name of the track
int played= 0; // The number of times played
int shuffleTag= 0; // For shuffling
musicNode next;

public musicNode() {        // Here's how we construct an empty list.
    next = null;
}
public musicNode(String t) {
    track = t; next = null;
}
public musicNode(String t, musicNode ptr) {
    track = t; next = ptr;
}

public boolean LTTrack(musicNode x) {   // Compares tracks according to alphabetical order on strings
    if (this.track.compareTo(x.track)<=0) return true;
    else return false;
}
}; 

// This class represents a playlist;
// We assume that each track appears at most once in the playlist

public class MusicPlayer {
protected musicNode head = null; // Pointer to the top of the list.
int length=0;   // the number of nodes in the list.
boolean debug= false;

public  MusicPlayer() {
}
public void setToNull() {
    head = null;
}
public boolean isEmpty() {
    return head == null;
}

public musicNode head() {
    return head;
}

void insertTrack(String name) { // Inserts a new track at the top of the list.
    musicNode temp= new musicNode(name, head);
    head= temp;
    length++;
}

void sortTrack() { // TODO
    musicNode main = this.head;
    mergeSort(main);
}


public musicNode mergeSort(musicNode head) {
    if ((head == null) || (head.next == null)){
        return head;
    }
    musicNode left = head;
    musicNode right = head.next;

    while((right != null) && (right.next != null)){
        head = head.next;
        right = (right.next).next;
    }
    right = head.next;
    head.next = null;

    return merge(mergeSort(left), mergeSort(right));
}

There also this JUnit test:

public void testSortMixed() {   
    MusicPlayer trackList= new MusicPlayer();
    trackList.insertTrack("d");
    trackList.insertTrack("b");
    trackList.insertTrack("e");
    trackList.insertTrack("a");
    trackList.insertTrack("c");

    MusicPlayer trackListTwo= new MusicPlayer();
    trackListTwo.insertTrack("e");
    trackListTwo.insertTrack("d");
    trackListTwo.insertTrack("c");
    trackListTwo.insertTrack("b");
    trackListTwo.insertTrack("a");

    trackList.sortTrack();
    musicNode tmp= trackList.head;
    musicNode tmp2= trackListTwo.head;
    for(int i=0; i< 5; i++){
        assertEquals(tmp2.track, tmp.track);
        tmp2= tmp2.next;
        tmp=tmp.next;
    }
}

The problem is that it sorts according to the last track you insert, and only from then on. So say you insert alphabets from a-f, but the last one you insert was "c", itll only show you "cdef". But if the last one was "a" then it works as intended.

So how it works is, when you insert a track it gets inserted onto the beginning of the list, not end, becoming the head. I feel like that may be whats messing it up, as I adapted and looked from my notes and online which insert at the bottom.

I dont know how to account for this though. Also I know it sorts based on what was inserted last (in the JUnit test above it sorts to "cde" because I created a main function and played around with it)

ANY help appreciated.

Answer 1

The key point is the second line in the method sortTrack:

void sortTrack() {
    musicNode main = this.head;
    this.head = mergeSort(main); // you forgot to set the head of linked list to the merged
}

I'd tested it in my laptop and everything goes okay now xD