git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 1/3] add mergesort() for linked lists

From
René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date
Apr 8, 2012, 20:32 UTC
Message-ID
<4F81F5E6.2070609@lsrfire.ath.cx>
In-Reply-To
<7vpqbm56pf.fsf@alter.siamese.dyndns.org>
Am 05.04.2012 21:17, schrieb Junio C Hamano:
> After seeing "I wrote it myself due to NIH", it strikes me a bit odd that
> you still used "start from bunch of singleton sublist, elongating twice
> per round as we go" structure from the original.

It's just becasue the dumb bottom-up approach is the most simple way to implement merge sort.

Show 23 quoted lines
> I wonder if it would be an improvement if you structured the loop so that:
> 
>   (1) the first sublist 'p' grabs as many elements in the ascending order
>       as you find;
> 
>   (2) the second sublist 'q' begins at the end of the first sublist and
>       grabs as many elements in the ascending order;
> 
>   (3) 'p' and 'q' are merge-sorted into the result list;
> 
>   (4) if your two sublists did not cover "list" in its entirety, process
>       the remainder (i.e. where the second sublist stopped because of an
>       unordered element) by going back to step (1); and
> 
>   (5) if you did not need to jump back to step (1) from step (4), then you
>       had only two sublists (or less), so the result is sorted.  Otherwise,
>       the result now has fewer ascending sublists than the original, so go
>       back to (1) and iterate.
> 
> If the input is in a random order, this may end up doing the same number
> of iterations as the original, but if the input is mostly sorted, wouldn't
> it allow us to take advantage of the fact by starting with a longer
> sublist in the earlier rounds?

This optimization speeds up the pre-sorted case but slows down the case of a reversed pre-sorted list because we have to determine the length of the sublists each time, while the dumb implementation already knows it. I didn't measure a significant difference for Jeff's test case. Here's my attempt at an implementation, for reference.

---
 mergesort.c |   61 +++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 41 insertions(+), 20 deletions(-)
diff --git a/mergesort.c b/mergesort.c
index c0f1874..3a61b9b 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -8,12 +8,37 @@ struct mergesort_sublist {
 	unsigned long len;
 };
 
-static void *get_nth_next(void *list, unsigned long n,
-			  void *(*get_next_fn)(const void *))
+static unsigned long run_length(const void *list,
+				struct mergesort_sublist *next_list,
+				void *(*get_next_fn)(const void *),
+				int (*compare_fn)(const void *, const void *))
 {
-	while (n-- && list)
-		list = get_next_fn(list);
-	return list;
+	unsigned long len = 1;
+
+	if (!list)
+		return 0;
+	for (;;) {
+		void *next = get_next_fn(list);
+
+		if (!next || compare_fn(list, next) > 0) {
+			if (next_list)
+				next_list->ptr = next;
+			break;
+		}
+		list = next;
+		len++;
+	}
+	return len;
+}
+
+static void set_next_pair(struct mergesort_sublist *p,
+			  struct mergesort_sublist *q, void *list,
+			  void *(*get_next_fn)(const void *),
+			  int (*compare_fn)(const void *, const void *))
+{
+	p->ptr = list;
+	p->len = run_length(p->ptr, q, get_next_fn, compare_fn);
+	q->len = q->ptr ? run_length(q->ptr, NULL, get_next_fn, compare_fn) : 0;
 }
 
 static void *pop_item(struct mergesort_sublist *l,
@@ -30,24 +55,16 @@ void *mergesort(void *list,
 		void (*set_next_fn)(void *, void *),
 		int (*compare_fn)(const void *, const void *))
 {
-	unsigned long l;
-
 	if (!list)
 		return NULL;
-	for (l = 1; ; l *= 2) {
+	for (;;) {
 		void *curr;
 		struct mergesort_sublist p, q;
 
-		p.ptr = list;
-		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+		set_next_pair(&p, &q, list, get_next_fn, compare_fn);
 		if (!q.ptr)
 			break;
-		p.len = q.len = l;
-
-		if (compare_fn(p.ptr, q.ptr) > 0)
-			list = curr = pop_item(&q, get_next_fn);
-		else
-			list = curr = pop_item(&p, get_next_fn);
+		list = curr = pop_item(&q, get_next_fn);
 
 		while (p.ptr) {
 			while (p.len || q.len) {
@@ -63,10 +80,14 @@ void *mergesort(void *list,
 					curr = pop_item(&p, get_next_fn);
 				set_next_fn(prev, curr);
 			}
-			p.ptr = q.ptr;
-			p.len = l;
-			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
-			q.len = q.ptr ? l : 0;
+
+			set_next_pair(&p, &q, q.ptr, get_next_fn, compare_fn);
+			if (q.ptr) {
+				void *prev = curr;
+
+				curr = pop_item(&q, get_next_fn);
+				set_next_fn(prev, curr);
+			}
 
 		}
 		set_next_fn(curr, NULL);

-- 
1.7.10
Previous: Junio C HamanoNext: Junio C Hamano
Message 9 of 37 in “Git push performance problems with ~100K refs”
  1. Martin FickMar 30, 2012
  2. Junio C HamanoMar 30, 2012
  3. Martin FickMar 30, 2012
  4. Jeff KingMar 30, 2012
  5. Jeff KingMar 30, 2012
  6. Martin FickMar 30, 2012
  7. 1/3 add mergesort() for linked listsRené Scharfe, Mar 31, 2012
  8. Junio C HamanoApr 5, 2012
  9. René ScharfeApr 8, 2012
  10. Junio C HamanoApr 9, 2012
  11. Stephen BoydApr 11, 2012
  12. Junio C HamanoApr 11, 2012
  13. 2/3 commit: use mergesort() in commit_list_sort_by_date()René Scharfe, Mar 31, 2012
  14. 3/3 revision: insert unsorted, then sort in prepare_revision_walk()René Scharfe, Mar 31, 2012
  15. Martin FickMar 31, 2012
  16. Junio C HamanoMar 31, 2012
  17. Martin FickApr 2, 2012
  18. Shawn PearceApr 2, 2012
  19. Martin FickApr 2, 2012
  20. Shawn PearceApr 2, 2012
  21. Jeff KingApr 2, 2012
  22. Jeff KingApr 2, 2012
  23. Martin FickApr 2, 2012
  24. Nguyen Thai Ngoc DuyApr 3, 2012
  25. Martin FickApr 3, 2012
  26. 0/3 Commit cacheNguyễn Thái Ngọc Duy, Apr 3, 2012
  27. 1/3 parse_commit_buffer: rename a confusing variable nameNguyễn Thái Ngọc Duy, Apr 3, 2012
  28. 2/3 Add commit cache to help speed up commit traversalNguyễn Thái Ngọc Duy, Apr 3, 2012
  29. 3/3 Add parse_commit_for_rev() to take advantage of sha1-cacheNguyễn Thái Ngọc Duy, Apr 3, 2012
  30. Nguyen Thai Ngoc DuyApr 5, 2012
  31. Shawn PearceApr 6, 2012
  32. Nguyen Thai Ngoc DuyApr 7, 2012
  33. Nguyen Thai Ngoc DuyApr 3, 2012
  34. Jeff KingApr 2, 2012
  35. René ScharfeApr 2, 2012
  36. Jeff KingApr 3, 2012
  37. Jeff KingApr 3, 2012

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.