diff --git a/usr.sbin/makefs/makefs.c b/usr.sbin/makefs/makefs.c
--- a/usr.sbin/makefs/makefs.c
+++ b/usr.sbin/makefs/makefs.c
@@ -43,6 +43,7 @@
 #include <ctype.h>
 #include <errno.h>
 #include <limits.h>
+#include <locale.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -103,6 +104,13 @@
 
 	setprogname(argv[0]);
 
+	/*
+	 * Set the locale for collation, so that directory entry sorting is
+	 * consistent.
+	 */
+	if (setlocale(LC_COLLATE, "C") == NULL)
+		err(1, "setlocale");
+
 	debug = 0;
 	if ((fstype = get_fstype(DEFAULT_FSTYPE)) == NULL)
 		errx(1, "Unknown default fs type `%s'.", DEFAULT_FSTYPE);
diff --git a/usr.sbin/makefs/walk.c b/usr.sbin/makefs/walk.c
--- a/usr.sbin/makefs/walk.c
+++ b/usr.sbin/makefs/walk.c
@@ -59,6 +59,50 @@
 static	fsnode	*create_fsnode(const char *, const char *, const char *,
 			       struct stat *);
 
+static int
+cmp(const void *_a, const void *_b)
+{
+	const fsnode * const *a = _a;
+	const fsnode * const *b = _b;
+
+	assert(strcmp((*a)->name, (*b)->name) != 0);
+	if (strcmp((*a)->name, ".") == 0)
+		return (-1);
+	if (strcmp((*b)->name, ".") == 0)
+		return (1);
+	return (strcoll((*a)->name, (*b)->name));
+}
+
+/*
+ * Sort the entries rather than relying on the order given by readdir(3),
+ * which might not be reproducible.
+ */
+static fsnode *
+sort_dir(fsnode *list)
+{
+	fsnode		**array;
+	fsnode		*cur;
+	size_t		nitems, i;
+
+	nitems = 0;
+	for (cur = list; cur != NULL; cur = cur->next)
+		nitems++;
+	assert(nitems > 0);
+
+	array = malloc(nitems * sizeof(fsnode *));
+	if (array == NULL)
+		err(1, "malloc");
+	for (i = 0, cur = list; cur != NULL; i++, cur = cur->next)
+		array[i] = cur;
+	qsort(array, nitems, sizeof(fsnode *), cmp);
+	for (i = 0; i < nitems; i++) {
+		array[i]->first = array[0];
+		array[i]->next = i == nitems - 1 ? NULL : array[i + 1];
+	}
+	cur = array[0];
+	free(array);
+	return (cur);
+}
 
 /*
  * walk_dir --
@@ -71,7 +115,7 @@
 fsnode *
 walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join)
 {
-	fsnode		*first, *cur, *prev, *last;
+	fsnode		*first, *cur;
 	DIR		*dirp;
 	struct dirent	*dent;
 	char		path[MAXPATHLEN + 1];
@@ -95,10 +139,8 @@
 		first = cur = join;
 		while (cur->next != NULL)
 			cur = cur->next;
-		prev = cur;
 	} else
-		first = prev = NULL;
-	last = prev;
+		first = NULL;
 	while ((dent = readdir(dirp)) != NULL) {
 		name = dent->d_name;
 		dot = 0;
@@ -136,10 +178,6 @@
 			for (;;) {
 				if (cur == NULL || strcmp(cur->name, name) == 0)
 					break;
-				if (cur == last) {
-					cur = NULL;
-					break;
-				}
 				cur = cur->next;
 			}
 			if (cur != NULL) {
@@ -160,24 +198,11 @@
 
 		cur = create_fsnode(root, dir, name, &stbuf);
 		cur->parent = parent;
-		if (dot) {
-				/* ensure "." is at the start of the list */
-			cur->next = first;
-			first = cur;
-			if (! prev)
-				prev = cur;
-			cur->first = first;
-		} else {			/* not "." */
-			if (prev)
-				prev->next = cur;
-			prev = cur;
-			if (!first)
-				first = cur;
-			cur->first = first;
-			if (S_ISDIR(cur->type)) {
-				cur->child = walk_dir(root, rp, cur, NULL);
-				continue;
-			}
+		cur->next = first;
+		first = cur;
+		if (!dot && S_ISDIR(cur->type)) {
+			cur->child = walk_dir(root, rp, cur, NULL);
+			continue;
 		}
 		if (stbuf.st_nlink > 1) {
 			fsinode	*curino;
@@ -204,13 +229,9 @@
 			cur->symlink = estrdup(slink);
 		}
 	}
-	assert(first != NULL);
-	if (join == NULL)
-		for (cur = first->next; cur != NULL; cur = cur->next)
-			cur->first = first;
 	if (closedir(dirp) == -1)
 		err(1, "Can't closedir `%s/%s'", root, dir);
-	return (first);
+	return (sort_dir(first));
 }
 
 static fsnode *