private void mergeSort(ListNode[] nodes, ListNode[] backup, int start,
			int end) {
		if (end - start == 1) {
			nodes[start].next = null;
			return;
		}

		int dist = end - start;
		int mid = dist >> 1;
		if (dist % 2 == 1) {
			mid += 1;
		}
		mid += start;
		// int mid = (end - start) / 2;

		mergeSort(nodes, backup, start, mid);
		mergeSort(nodes, backup, mid, end);
		ListNode a = nodes[start];
		ListNode b = nodes[mid];
		int idx = start;
		while (a != null && b != null) {
			if (a.val <= b.val) {
				backup[idx++] = a;
				a = a.next;
			} else {
				backup[idx++] = b;
				b = b.next;
			}
		}

		while (a != null) {
			backup[idx++] = a;
			a = a.next;
		}

		while (b != null) {
			backup[idx++] = b;
			b = b.next;
		}

		nodes[start] = backup[start];
		for (int i = start + 1; i < end; i++) {
			ListNode x = backup[i - 1];
			ListNode y = backup[i];
			x.next = y;
			nodes[i] = y;
		}
		nodes[end - 1].next = null;
	}